本文主要是介绍算法训练day63完结撒花单调栈739每日温度496下一个更大的元素503下一个更大的元素二,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
739每日温度
什么时候用单调栈
通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。
#include <iostream>
#include <vector>
#include <stack>class Solution {
public:std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {std::vector<int> result(temperatures.size(), 0);std::stack<int> stk;if (!temperatures.empty()) {stk.push(0);}for (int i = 1; i < temperatures.size(); i++) {if (temperatures[i] <= temperatures[stk.top()]) stk.push(i);else {while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {result[stk.top()] = i - stk.top();stk.pop();}stk.push(i);}}return result;}
};int main() {Solution sol;std::vector<int> tem = {73,74,75,71,69,72,76,73};std::vector<int> res = sol.dailyTemperatures(tem);for (int i: res) {std::cout << i << " " ;}return 0;
}
单调栈里面的元素单调递增或单调递减
496下一个更大的元素
单调栈的本质是空间换时间。单调栈的作用就是存放遍历过的元素
递增就是求第一个比他大的元素的位置,递减就是求第一个比他小的元素的位置
将当前元素和栈口元素做比较 T[i] 和T[st.top()],再用一个result数组来记录reslult[st.top()]
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>class Solution {
public:std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {std::unordered_map<int, int> umap;for (int i = 0; i < nums1.size();i ++) {umap[nums1[i]] = i;}std::vector<int> result(nums1.size(), -1);std::stack<int> stk;stk.push(0);for (int i = 1; i < nums2.size(); i++) {if (nums2[i] <= nums2[stk.top()]) {stk.push(i);}else {while (!stk.empty() && nums2[i] > nums2[stk.top()]) {if (umap.find(nums2[stk.top()]) != umap.end()) {result[umap[nums2[stk.top()]]] = nums2[i];}stk.pop();}stk.push(i);}}return result;}
};int main() {Solution sol;std::vector<int> nums1 = {2,4};std::vector<int> nums2 = { 1,2,3,4};std::vector<int> res= sol.nextGreaterElement(nums1, nums2);for (int i : res) {std::cout << i << "," ;}return 0;}
503下一个更大的元素二
处理循环数组,可以不扩充nums,而是在遍历的过程中模拟走了两边nums。模拟遍历两边nums,注意一下都是用i % nums.size()来操作\
#include <iostream>
#include <vector>
#include <stack>class Solution {
public:std::vector<int> nextGreaterElements(std::vector<int>& nums) {std::stack<int> stk;std::vector<int> result(nums.size(), -1);stk.push(0);for (int i = 1 ; i < 2*nums.size(); i ++) {if (nums[i % nums.size()] <= nums[stk.top()]) {stk.push(i % nums.size());}else {while (!stk.empty() && nums[i % nums.size()] > nums[stk.top()]) {result[stk.top()] = nums[i % nums.size()];stk.pop();}stk.push(i % nums.size());}}return result;}
};int main() {Solution sol;std::vector<int> nums = {1,2,1};std::vector<int> res = sol.nextGreaterElements(nums);for (int i : res) {std::cout << i << " ";}return 0;
}
易错点为while (!stk.empty() && nums2[i] > nums2[stk.top()])容易忘记!stk.empty()
这篇关于算法训练day63完结撒花单调栈739每日温度496下一个更大的元素503下一个更大的元素二的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!