单调栈问题

什么是单调栈

维护一个栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性

84、柱状图中最大的矩形

解法一：暴力法（超时）

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if(len == 1) return heights[0];
        int maxArea = 0;
        for (int i = 0;i < len;i++){
            System.out.println("i = " + i);
            int left = i;
            int right = i;
            for(int j = i - 1;j >= 0;j--){
                if(heights[j] < heights[i]){
                    left = j;
                    break;
                }
                else{
                    left = -1;
                    //假设之前还有一个比heights【i】小
                }
            }
            for(int k = i + 1;k < len;k++){
                if(heights[k] < heights[i]){
                    right = k ;
                    break;
                }
                else{

                    right = len;
                }
            }
            System.out.println("left = "+ left);
            System.out.println("right = "+ right);
            int Area = 0;
            if(left != i && right != i){
                Area = heights[i] * (right - left - 1);
            }
            else if((left == i && right != i) || (left != i && right == i) ){
                Area = heights[i] * (right - left);
            }
            else if(left - right == 0 ){
                Area = heights[i];
            }
            System.out.println("Area = "+ Area);
            maxArea = Area > maxArea? Area:maxArea;
        }
        return maxArea;

    }
}

解法二：符合后进先出规律，使用栈

栈存放下标，并且对应的高度按从小到大顺序排列

遍历每个高度，如果当前高度比栈顶的高度大，将当前下标入栈，否则，将栈顶元素出栈（这个高度矩形的面积已经可以确定），如果栈顶出栈后栈空，意味着之前没有比他小的柱形，即这个高度的矩形可以扩展到最左边，即width = i。如果出栈后栈不为空，说明新栈顶就是栈顶(已出栈）该高度的左边界，即width = i - stack.peekLast() - 1 ,记录过程中的最大面积。

遍历结束后，如果此时栈不为空，并且已知栈内高度从小到大排列，所以可以得出每一个高度的矩形都可以扩展道最右边。在对宽度Width的计算中，只需把i替换成数组长度len。

最后返回最大面积

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        //特判
        if(len == 0){
            return 0;
        }
        if(len == 1){
            return heights[0];
        }
        
        Deque<Integer> stack = new ArrayDeque<>();
        int area = 0;
        //遍历每个高度
        for(int i = 0;i < len;i++){
            int now = heights[i];
            while(!stack.isEmpty() && now < heights[stack.peekLast()]){
                int height = heights[stack.removeLast()];

                //相同的话将栈顶元素弹出
                while(!stack.isEmpty() && heights[stack.peekLast()] == height){
                    stack.removeLast();
                }
                int width;
                //栈为空说明没有比这个高度更小的柱形，即这个高度的柱形可以扩展到最左边
                if(stack.isEmpty()){
                    width = i;
                }else {
                    width = i - stack.peekLast() - 1;
                }

                area = Math.max(area,height * width);
            }
            //当前高度比栈顶的高度大，入栈
            stack.addLast(i);
        }

        while(!stack.isEmpty()){
            int height = heights[stack.removeLast()];

            //相同的话将栈顶元素弹出
            while(!stack.isEmpty() && heights[stack.peekLast()] == height){
                stack.removeLast();
            }
            int width;
            //栈为空说明没有比这个高度更小的柱形，即这个高度的柱形可以扩展到最左边
            if(stack.isEmpty()){
                width = len;
            }else {
                width = len - stack.peekLast() - 1;
            }

            area = Math.max(area,height * width);
        }

        return area;
        }
}

解法二优化：使用哨兵节点

加入哨兵节点即在数组首尾加入一个高度为0的柱形

哨兵1可以保证栈非空，从而可以在代码逻辑中删去所有判断栈为空的操作

哨兵2可以保证一轮遍历结束后，计算出的最大面积即为所求，省去了上面遍历结束后弹栈的操作。因为有哨兵2的存在，它比栈内所有的高度都小，都要进行弹栈操作。简化代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if(len == 0){
            return 0;
        }
        if(len == 1){
            return heights[0];
        }
        int[] Heights = new int[len + 2];
        for(int i = 0;i < len ;i++){
            Heights[i + 1] = heights[i];
        }
        len += 2;
        heights = Heights;
        int area = 0;

        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(0);//加入哨兵节点，保证栈非空
        for(int i = 1;i < len;i++){
            while( heights[i] < heights[stack.peekLast()]){
                int height = heights[stack.removeLast()];
                int width = i - stack.peekLast() - 1;
                area = Math.max(area,height * width);
            }
            stack.addLast(i);
        }
        return area;
        }
}

496、下一个更大元素Ⅰ

法一、暴力法

hashmap保存数组nums2中元素及对应的下标

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] result = new int[nums1.length];
        Arrays.fill(result,-1);
        for(int i = 0;i < nums2.length;i++){
            map.put(nums2[i],i);
        }
        for(int i =0;i < nums1.length;i++){
            int location = map.get(nums1[i]);
            for(int j = location;j < nums2.length;j++){
                if(nums2[j] > nums1[i]){
                    result[i] = nums2[j];
                    break;
                }
            }
        }
    return result;
    }

法二：单调栈

维护一个单调递减的栈，如果遇到了大于栈顶元素的值，那么这个值一定是栈顶元素的下一个更大的元素。将栈顶元素弹出，写入map。最后将数组元素遍历结束，如果栈不为空，说明站内元素找不到更大的元素，即为-1

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            HashMap<Integer,Integer> map = new HashMap<>();
            Stack<Integer> stack = new Stack<>();
            int[] result = new int[nums1.length];
            for(int i = 0;i < nums2.length;i++){
                while (!stack.isEmpty() && stack.peek() < nums2[i]){
                    map.put(stack.pop(),nums2[i]);
                }
                stack.push(nums2[i]);
            }
            while (!stack.isEmpty()){
                map.put(stack.pop(),-1);
            }
            for(int i = 0;i < nums1.length;i++){
                result[i] = map.get(nums1[i]);
            }
            return result;

        }
}

739、每日温度

简简单单

一开始傻乎乎地将数组元素值存进栈，之后在知元素值求下表问题上出错，因为我是用map<T[i],i>存储，而给定数组中可以出现重复温度，这些重复温度在map中仅记录最新值。

应该为存放下标

我用的是Stack<>集合，提交只击败24%

官方题解使用队列模拟栈Deque<Integer> stack = new LinkedList<Integer>();。击败76%，记录学习

class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[T.length];
        Arrays.fill(result,0);

        for(int i = 0;i < T.length;i++){
            while (!stack.isEmpty() && T[stack.peek()] < T[i]){
                //int j = stack.pop();
                result[stack.peek()] = i - stack.pop() ;
            }
            stack.push(i);
        }
        return result;

    }
}

问题：

Leetcode 42 接雨水

Leetcode 503 下一个更大元素||