本文主要是介绍代码随想录笔记--单调栈篇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1--单调栈
使用单调栈的特征：寻找第一个比当前元素大或者小的元素。
2--每日温度
主要思路：
基于单调栈，单调栈从栈顶开始递增；单调栈存储的是元素对应的索引。
当遇到一个元素大于栈顶元素i时，计算 answer[i]。
#include <iostream>
#include <vector>
#include <stack>class Solution {
public:std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {std::vector<int> res(temperatures.size(), 0);std::stack<int> stk;for(int i = 0; i < temperatures.size(); i++){while(!stk.empty() && temperatures[i] > temperatures[stk.top()]){res[stk.top()] = i - stk.top();stk.pop();}stk.push(i);}return res;}
};int main(int argc, char* argv[]){// temperatures = [73,74,75,71,69,72,76,73]std::vector<int> test = {73, 74, 75, 71, 69, 72, 76, 73};Solution S1;std::vector<int> res = S1.dailyTemperatures(test);for(auto num : res) std::cout << num << " ";std::cout << std::endl;return 0;
}3--下一个更大元素I
主要思路：
基于单调栈和哈希表。
将 nums1 的元素映射为哈希表，其中 key 为 num1[i]，val 为 i；
遍历 nums2 构建单调栈，当 nums2[i] > stk.top() 时，且 stk.top() 属于 nums1，表明找到第一个比它大的元素，则根据hash_map[stk.top()]可以知道其在nums1的位置，记录结果res[hash_map[stk.top()]] = nums2[i] 即可。
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>class Solution {
public:std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {std::vector<int> res(nums1.size(), -1);if(nums1.size() == 0) return res;std::unordered_map<int, int>hash_map;for(int i = 0; i < nums1.size(); i++) hash_map.emplace(nums1[i], i); // 存储值，索引std::stack<int> stk;for(int i = 0; i < nums2.size(); i++){while(!stk.empty() && nums2[i] > stk.top()){if(hash_map.find(stk.top()) != hash_map.end()){res[hash_map[stk.top()]] = nums2[i];}stk.pop();}stk.push(nums2[i]);}return res;}
};int main(int argc, char* argv[]){// nums1 = [4,1,2], nums2 = [1,3,4,2]std::vector<int> test1 = {4, 1, 2};std::vector<int> test2 = {1, 3, 4, 2};Solution S1;std::vector<int> res = S1.nextGreaterElement(test1, test2);for(auto num : res) std::cout << num << " ";std::cout << std::endl;return 0;
}3--下一个更大元素II
主要思路：
基于单调栈，本题的难点是针对一个循环数组，可以通过取模的操作来模拟循环数组。
#include <iostream>
#include <vector>
#include <stack>class Solution {
public:std::vector<int> nextGreaterElements(std::vector<int>& nums) {std::vector<int> res(nums.size(), -1);std::stack<int> stk;for(int i = 0; i < 2*nums.size(); i++){// 通过取模操作模拟有环的过程int idx = i % nums.size();while(!stk.empty() && nums[idx] > nums[stk.top()]){res[stk.top()] = nums[idx];stk.pop();}stk.push(idx);}return res;}
};int main(int argc, char* argv[]){// nums = [1, 2, 1]std::vector<int> test = {1, 2, 1};Solution S1;std::vector<int> res = S1.nextGreaterElements(test);for(int num : res) std::cout << num << " ";std::cout << std::endl;return 0;
}这篇关于代码随想录笔记--单调栈篇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
