栈（stack）是很简单的⼀种数据结构，先进后出的逻辑顺序，符合某些问题的特点，⽐如说函数调⽤栈。单
调栈实际上就是栈，只是利⽤了⼀些巧妙的逻辑，使得每次新元素⼊栈后，栈内的元素都保持有序（单调递
增或单调递减）。单调栈⽤途不太⼴泛，只处理⼀类典型的问题，⽐如「下⼀个更⼤元素」，「上⼀个更⼩元素」等。

这三道题，基本都是用的模板，做题顺序是496 -> 739 -> 503。

单调栈模版

现在给你出这么⼀道题：输⼊⼀个数组 nums，请你返回⼀个等⻓的结果数组，结果数组中对应索引存储着下
⼀个更⼤元素，如果没有更⼤的元素，就存 -1。函数签名如下：

  1. int[] nextGreaterElement(int[] nums);

⽐如说，输⼊⼀个数组 nums = [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。因为第⼀个 2 后⾯⽐ 2 ⼤的数是 4; 1 后⾯⽐ 1 ⼤的数是 2；第⼆个 2 后⾯⽐ 2 ⼤的数是 4; 4 后⾯没有⽐ 4 ⼤的数，填 -1；3 后⾯没有⽐ 3 ⼤的数，填 -1。

这个问题可以这样抽象思考：把数组的元素想象成并列站⽴的⼈，元素⼤⼩想象成⼈的身⾼。这些⼈⾯对你站成⼀列，如何求元素「2」的下⼀个更⼤元素呢？很简单，如果能够看到元素「2」，那么他后⾯可⻅的第⼀个⼈就是「2」的下⼀个更⼤元素，因为⽐「2」⼩的元素身⾼不够，都被「2」挡住了，第⼀个露出来的就是答案。
image.png
这个情景很好理解吧？带着这个抽象的情景，先来看下代码。

  1. int[] nextGreaterElement(int[] nums){
  2.     int n = nums.length;
  3.     //存放答案的数组
  4.     int res = new int[n];
  6.     Stack<Integer> s = new Stack<>();
  8.     //倒着往栈里放
  9.     for(int i = n-1; i >= 0; i--){
  10.         //判定格子高矮
  11.         while(!s.isEmpty() && s.peek() <= nums[i]){
  12.             //矮子直接出栈，反正也被挡住了
  13.             s.pop();
  14.         }
  15.         //nums[i]身后的更大元素
  16.         res[i] = s.isEmpty() ? -1 : s.peek();
  17.         s.push(nums[i]);
  18.     }
  20.     return res;
  21. }

496. 下一个更大元素 I

把模板改一改就可以解决这道题，因为题目中说了nums1是nums2的子集，那么我就先把nums2中每一个元素的下一个更大的元素算出来，存到一个映射中，然后再让nums1中的元素去查表即可，因为是子集的缘故所以不用担心找不到key的情况。

  1. public int[] nextGreaterElement(int[] nums1, int[] nums2) {
  2.     //记录 nums2 中每一个元素的下一个更大元素
  3.     int[] greater = nextGreaterElement(nums2);
  5.     //转换成映射：元素 x -> x的下一个最大元素
  6.     HashMap<Integer, Integer> greaterMap = new HashMap<>();
  7.     for(int i = 0; i < nums2.length; i++){
  8.         greaterMap.put(nums2[i], greater[i]);
  9.     }
  11.     //nums1 是 nums2 的子集，所以根据greaterMap可以得到结果
  12.     //不存在没有对应的key的情况
  13.     int[] res = new int[nums1.length];
  14.     for(int i = 0; i < nums1.length; i++){
  15.         res[i] = greaterMap.get(nums1[i]);
  16.     }
  18.     return res;
  19. }
  21. int[] nextGreaterElement(int[] nums){
  22.     int n = nums.length;
  23.     //存放答案的数组
  24.     int[] res = new int[n];
  26.     Stack<Integer> s = new Stack<>();
  28.     //倒着往栈里放
  29.     for(int i = n-1; i >= 0; i--){
  30.         //判定格子高矮
  31.         while(!s.isEmpty() && s.peek() <= nums[i]){
  32.             //矮子直接出栈，反正也被挡住了
  33.             s.pop();
  34.         }
  35.         //nums[i]身后的更大元素
  36.         res[i] = s.isEmpty() ? -1 : s.peek();
  37.         s.push(nums[i]);
  38.     }
  40.     return res;
  41. }

739. 每日温度

这个问题本质上也是找下⼀个更⼤元素，只不过现在不是问你下⼀个更⼤元素的值是多少，⽽是问你当前元素距离下⼀个更⼤元素的索引距离⽽已。

  1. public int[] dailyTemperatures(int[] temperatures) {
  2.     int n = temperatures.length;
  3.     int[] res = new int[n];
  5.     //这里放索引，而不是元素
  6.     Stack<Integer> s = new Stack<>();
  8.     //单调栈模版
  9.     for(int i = n-1; i >= 0; i--){
  10.         while(!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]){
  11.             s.pop();
  12.         }
  14.         //得到索引间距，s.peek()是更暖和的天气的索引，i是当前天气的索引
  15.         res[i] = s.isEmpty() ? 0 : (s.peek() - i);
  16.         //将索引入栈，而不是元素
  17.         s.push(i);
  18.     }
  20.     return res;
  21. }

503. 下一个更大元素 II

这道题的难点是如何处理环形数组。我们⼀般是通过 % 运算符求模（余数），来模拟环形特效:

  1. int[] arr = {1,2,3,4,5};
  2. int n = arr.length, index = 0;
  3. while (true) {
  4.     // 在环形数组中转圈
  5.     print(arr[index % n]);
  6.     index++;
  7. }

这个问题肯定还是要⽤单调栈的解题模板，但难点在于，⽐如输⼊是 [2,1,2,4,3]，对于最后⼀个元素 3，
如何找到元素 4 作为下⼀个更⼤元素。
对于这种需求，常⽤套路就是将数组长度翻倍：
image.png
这样，元素 3 就可以找到元素 4 作为下⼀个更⼤元素了，⽽且其他的元素都可以被正确地计算。
有了思路，最简单的实现⽅式当然可以把这个双倍⻓度的数组构造出来，然后套⽤算法模板。但是，我们可
以不⽤构造新数组，⽽是利⽤循环数组的技巧来模拟数组⻓度翻倍的效果。

  1. public int[] nextGreaterElements(int[] nums) {
  2.     int n = nums.length;
  3.     int[] res = new int[n];
  5.     Stack<Integer> s = new Stack<>();
  7.     //数组长度加倍模拟环形数组
  8.     for(int i = 2*n-1; i >= 0; i--){
  9.         //索引i要求模，其他的和模板一样
  10.         while(!s.isEmpty() && s.peek() <= nums[i % n]){
  11.             s.pop();
  12.         }
  13.         res[i % n] = s.isEmpty() ? -1 : s.peek();
  14.         s.push(nums[i % n]);
  15.     }
  17.     return res;
  18. }