代码随想录算法训练营第五十八天 _ 单调栈_155. 最小栈、739.每日温度、496. 下一个更大元素 I、503.下一个更大元素II。

本文主要是介绍代码随想录算法训练营第五十八天 _ 单调栈_155. 最小栈、739.每日温度、496. 下一个更大元素 I、503.下一个更大元素II。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

学习目标：

单调栈是一种特殊的栈数据结构，在栈的基础上增加了一些特定的性质。它主要用于解决一类与元素大小和顺序有关的问题。

特点：
单调递增栈：栈内元素从栈底到栈顶呈递增的顺序。
单调递减栈：栈内元素从栈底到栈顶呈递减的顺序。
实现步骤和规则：
遍历数组或列表：单调栈通常是通过遍历数组或列表实现的，根据特定条件入栈或出栈。
维护单调性：根据问题的需求，维护栈内元素的单调性（递增或递减）。
元素的入栈和出栈：根据当前元素和栈顶元素的比较，决定入栈或出栈的规则。
入栈规则：当前元素满足单调性条件时，入栈。
出栈规则：当前元素破坏单调性条件时，栈顶元素出栈，直到满足单调性条件为止，再将当前元素入栈。

60天训练营打卡计划！

学习内容：

155. 最小栈

好像和单调栈没什么关系，但是这个思路值得学习
当栈中的最大或最小值要更新时，在栈中保存前一个最大或最小值。

class MinStack {// 正式栈Stack<Integer> stk;int min;public MinStack() {stk = new Stack<>();min = Integer.MAX_VALUE;}public void push(int val) {// 使用栈将前一个最小值保存if(min >= val){stk.push(min);min = val;}stk.push(val);}public void pop() {// 将栈中存的上一次的最小值取出if(stk.peek() == min){stk.pop();min = stk.peek();}stk.pop();}public int top() {return stk.peek();}public int getMin() {return min;}
}

739.每日温度

单调栈作用：记录遍历过且没有被计算的元素下标
单调栈顺序：升序
场景：
① T[i] > T[st.peek()] — while循环
res[st.peek()] = i - st.peek()
st.pop()
② T[i] <= T[st.peek()] — 构造出了上升栈
st.push(i)

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];// 上升的单调栈：存的是遍历过的但未处理的元素下标Stack<Integer> st = new Stack<>();st.push(0);for(int i = 1; i < temperatures.length; i++){if(st.empty() || temperatures[i] <= temperatures[st.peek()]){st.push(i); // System.out.println("*# " + st.peek() + " " + i);}   else{while(!st.empty() && temperatures[i] > temperatures[st.peek()]){// System.out.println("* " + st.peek() + " " + i);res[st.peek()] = i - st.peek();st.pop();}// 都出站后要将i入栈st.push(i);}}return res;}
}

496. 下一个更大元素 I

单调栈作用：记录遍历过且没有被计算的元素下标
单调栈顺序：升序
场景：
① nums2[i] > nums2[st.peek()] — while循环
if(nums1数组中含该st.peek())
res[nums1数组中该st.peek()的位置] = nums2[i]
st.pop()
② nums2[i] < nums2[st.peek()] — 构造出了上升栈(nums2中所有整数互不相同)
st.push(i)

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 找不到的位置返回-1，所以直接初始化为-1int[] res = new int[nums1.length];Arrays.fill(res, -1);// 构造一个map映射nums1的值和位置关系，便于查询HashMap<Integer,Integer> map = new HashMap<>();for(int i = 0; i < nums1.length; i++){map.put(nums1[i],i);}// 构造一个递增的上升栈,存的是下标Stack<Integer> stk = new Stack<>();stk.push(0);for(int i = 1; i < nums2.length; i++){if(nums2[i] < nums2[stk.peek()])  stk.push(i);else{while(!stk.empty() && nums2[i] > nums2[stk.peek()]){// 当map中可以找到栈顶元素时，生成一个该值对应的下标的结果数组。// 与739每日温度的唯一区别if(map.containsKey(nums2[stk.peek()])){res[map.get(nums2[stk.peek()])] = nums2[i];}stk.pop();}// 一定要记得将i这个未处理的值加入到栈中，符合单调栈的结构stk.push(i);}}return res;}
}

503.下一个更大元素II

与739的区别是：该题目的数组是循环的。
所有的成环的数组都可以在遍历时对其取模实现原地循环！

for(int i = 1; i < nums.length * 2; i++){nums[i%(nums.length)]
}

单调栈作用：记录遍历过且没有被计算的元素下标
单调栈顺序：升序
场景：
① nums[i%(nums.length)] > nums[st.peek()] — while循环
res[st.peek()] = nums[i]
st.pop()
② nums[i%(nums.length)] <= nums[st.peek()] — 构造出了上升栈
st.push(i%(nums.length))

class Solution {public int[] nextGreaterElements(int[] nums) {    // 找不到的位置返回-1，所以直接初始化为-1int[] res = new int[nums.length];Arrays.fill(res, -1);// 构造一个递增的上升栈,存的是下标Stack<Integer> stk = new Stack<>();stk.push(0);for(int i = 1; i < nums.length*2; i++){if(nums[i%nums.length] <= nums[stk.peek()])   stk.push(i%nums.length);else{while(!stk.empty() && nums[i%nums.length] > nums[stk.peek()]){res[stk.peek()] = nums[i%nums.length];stk.pop();}// 一定要记得将i这个未处理的值加入到栈中，符合单调栈的结构stk.push(i%nums.length);}}return res;}
}