力扣-Hot100-栈【算法学习day.40】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.最小栈

题目链接:155. 最小栈 - 力扣（LeetCode）

题面:

分析:其他好说，需要思考的是如何快速获得最小值，我们可以定义一个数组用来存储从栈底到栈顶所有元素的最小值，在每次添加新元素时维护这个数组，代码具体如下:

代码:

class MinStack {
    int[] stack;
    int r;
    int[] min;    
    public MinStack() {
    stack = new int[30005];
    min = new int[30005];
    r = 0;
    }
    
    public void push(int val) {
        if(r==0){
            min[0] = val;
        }else{
            min[r] = Math.min(val,min[r-1]);
        }
        stack[r++] = val;
    }
    
    public void pop() {
        r--;
    }
    
    public int top() {
        return stack[r-1];
    }
    
    public int getMin() {
        return min[r-1];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

2.字符串解码

题目链接:394. 字符串解码 - 力扣（LeetCode）

题面:

基本分析:这题我是通过递归来模拟解码过程，例如示例一，遇到数字，则递归到下一层，拿到返回的字符串，拼接次数为数字

class Solution {
    int l = 0;
    int n;
    char[] chars;
    public String decodeString(String s) {
        chars = s.toCharArray();
        n = chars.length;
        String ans = "";
        while(l<n){
            ans+=recursion();
        }
        return ans;
    }

    public String recursion(){
        String ans = "";
        while(l<n){
            if(chars[l]>'0'&&chars[l]<='9'){
                int flag = 0;
                while(chars[l]>='0'&&chars[l]<='9'){
                    flag = flag*10+(chars[l]-'0');
                    l++;
                }
                l++;
                String s = recursion();
                for(int i = 0;i<flag;i++){
                    ans+=s;
                }
            }
            else if(chars[l]>='a'&&chars[l]<='z'){
                ans+=chars[l];
                l++;
            }
            else if(chars[l]==']'){
                l++;
                return ans;
            }else{
                l++;
            }
        }
        return ans;
    }
}

3.每日温度

题目链接:739. 每日温度 - 力扣（LeetCode）

题面:

基本分析:利用单调栈，从右向前遍历，如果栈中存在元素，就从栈中找到比当前元素更大的元素（如果没有，直到栈为空），每次循环结束将当前元素下标存入栈中

代码:

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        int[] stack = new int[n];
        int r = 0;
         for(int i = n-1;i>=0;i--){
            while(r>0&&temperatures[stack[r-1]]<=temperatures[i]){
                r--;
            }
            if(r>0){
                ans[i] = stack[r-1] - i;
            }
            stack[r++] = i;
         }
        
        return ans;

    }
}

4.柱状图中最大的矩形

题目链接:84. 柱状图中最大的矩形 - 力扣（LeetCode）

题面:

附上灵神双单调栈代码:

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            int x = heights[i];
            while (!st.isEmpty() && x <= heights[st.peek()]) {
                st.pop();
            }
            left[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }

        int[] right = new int[n];
        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            int x = heights[i];
            while (!st.isEmpty() && x <= heights[st.peek()]) {
                st.pop();
            }
            right[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }
}