单调栈

每日温度

描述：

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

示例：

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

思路：

​ 单调栈通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，就可以用单调栈了。

​ 单调栈里只需要存放元素的下标i就可以了。

解法：

var dailyTemperatures = function(temperatures){
    let n = temperatures.length;
    let res = new Array(n).fill(0);
    let stack = [];
    stack.push(0);
    for(let i=1;i<n;i++){
        let top = stack[stack.length-1];
        if(temperatures[i]<=temperatures[top])
            stack.push(i);
        else{
            while(stack.length&&temperatures[i]>temperatures[top]){
                top = stack.pop();
                res[top] = i-top;
            }
            stack.push(i);
        }
    }
    return res;
}

下一个更大元素I

描述：

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例：

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字1，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1 。

思路：

​ 递增栈能找到右边第一个比自己大的元素；递减栈能找到右边第一个比自己小的元素。

解法：

var nextGreaterElement = function(nums1, nums2){
    let stack = [0];
    let res = new Array(nums1.length).fill(-1);
    if(nums1.length===0)
        return res;
    let map = new Map();
    //不能直接map={}，这样在存数字key的时候key会变成字符串形式，取的时候也会出问题
    for(let i=0;i<nums1.length;i++)
        map.set(nums1[i], i);
    for(let i=1;i<nums2.length;i++){
        if(nums2[i]<=nums2[stack[stack.length-1]])
            stack.push(i);
        else{
            while(stack.length&&nums2[i]>nums2[stack[stack.length-1]]){
                if(map.has(nums2[stack[stack.length-1]])){
                    let index = map.get(nums2[stack[stack.length-1]]);
                    res[index] = nums2[i];
                }
                stack.pop();
            }
            stack.push(i);
        }
    }
    return res;
}

下一个更大元素II

描述：

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例：

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

思路：

​ 把两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。

解法：

var nextGreaterElement = function(nums){
    let len = nums.length;
    let stack = [];
    let res = new Array(len).fill(-1);
    for(let i=0;i<len*2;i++){
        while(stack.length&&nums[i%len]>nums[stack[stack.length-1]]){
            const index = stack.pop();
            res[index] = nums[i%len];
        }
        stack.push(i%len);
    }
    return res;
}

接雨水

描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

思路：

​ 从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。用单调栈，其实是通过 长 * 宽 来计算雨水面积的。

​ 使用栈顶和栈顶的下一个元素以及要入栈的三个元素来接水。

雨水的高度是min(凹槽左边的高度，凹槽右边的高度)-凹槽底部高度；雨水的宽度是凹槽右边的下标-凹槽左边的下标-1.

解法：

var trap = function(height){
    let len = height.length;
    if(len<=2)
        return 0;
    let stack = [0];
    let sum = 0;
    for(let i=1;i<len;i++){
        if(height[i]<height[stack[stack.length-1]])
            stack.push(i);
        else if(height[i]===height[stack[stack.length-1]]){
            stack.pop();
            stack.push(i);
        }else{
            while(stack.length&&height[i]>height[stack[stack.length-1]]){
                let mid = stack[stack.length-1];
                stack.pop();
                if(stack.length){
                    let h=Math.min(height[stack[stack.length-1]], height[i])-height[mid];
                    let w=i-stack[stack.length-1]-1;
                    sum+=w*h;
                }
            }
            stack.push(i);
        }
    }
    return sum;
}

柱状图中最大的矩形

描述：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例：

思路：

​ 本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！栈顶和栈顶的下一个元素以及要入栈的三个元素组成了要求的最大面积的高度和宽度

解法：

var largestRectangleArea = function(heights){
    let maxArea = 0;
    let stack = [];
    // 数组头部和尾部加零
    heights = [0, ...heights, 0];
    for(let i=0;i<heights.length;i++){
        if(heights[i]>heights[stack[stack.length-1]])
            stack.push(i);
        else if(heights[i]===heights[stack[stack.length-1]]){
            stack.pop();
            stack.push(i);
        }else{
            while(stack.length&&heights[i]<heights[stack[stack.length-1]]){
                let index = stack.pop();
                let w = i-stack[stack.length-1]-1;
                let h = heights[index];
                maxArea = Math.max(maxArea, w*h);
            }
            stack.push(i);
        }
    }
    return maxArea;
}