【LeetCode Hot100】栈篇

前言

        本文用于整理LeetCode Hot100中题目解答，因题目比较简单且更多是为了面试快速写出正确思路，只做简单题意解读和一句话题解方便记忆。但代码会全部给出，方便大家整理代码思路。

20. 有效的括号

一句话题意

        验证括号序列有效性。

一句话题解

        用双向队列模拟栈，然后验证即可。

class Solution {
    public boolean isValid(String s) {
        Deque<Character> q = new LinkedList<>();
        for(char c:s.toCharArray()){
            if(c==']'){
                if(q.size()==0)return false;
                char cc = q.pollFirst();
                if(cc=='[')continue;
                return false;
            }else if(c==')'){
                if(q.size()==0)return false;
                char cc = q.pollFirst();
                if(cc=='(')continue;
                return false;
            }else if(c=='}'){
                if(q.size()==0)return false;
                char cc = q.pollFirst();
                if(cc=='{')continue;
                return false;
            }
            q.addFirst(c);
        }
        return q.size() == 0;
    }
}

155. 最小栈

一句话题意

        要求实现一个数据结构。

        实现 MinStack 类:

• MinStack() 初始化堆栈对象。

• void push(int val) 将元素val推入堆栈。

• void pop() 删除堆栈顶部的元素。

• int top() 获取堆栈顶部的元素。

• int getMin() 获取堆栈中的最小元素。

一句话题解

        用两个双向队列，一个模拟栈，一个模拟对应的单调栈，每次往最小值。

class MinStack {
    Deque<Integer> u;
    Deque<Integer> umn;

    public MinStack() {
        u=new LinkedList<Integer>();
        umn=new LinkedList<Integer>();
    }
    
    public void push(int val) {
        u.addFirst(val);
        if(umn.size()==0)umn.addFirst(val);
        else umn.addFirst(Math.min(val,umn.peekFirst()));
    }
    
    public void pop() {
        if(u.size()!=0){
            u.pollFirst();
            umn.pollFirst();
        }
    }
    
    public int top() {
        return u.peekFirst();
    }
    
    public int getMin() {
        return umn.peekFirst();
    }
}

394. 字符串解码

一句话题意

        编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

        给定编码规则，问原先的字符串是什么。

一句话题解

        栈模拟，注意代码细节。

class Solution {
    public String decodeString(String s) {
        Deque<StringBuffer> q = new LinkedList<>();
        q.addFirst(new StringBuffer("!"));
        for(char c:s.toCharArray()){
            if(c>='0'&&c<='9'){
                char cc=q.peekFirst().charAt(0);
                if(cc>='0'&&cc<='9')q.addFirst(q.pollFirst().append(c));
                else q.addFirst(new StringBuffer().append(c));
            }else if(c=='['){
                q.addFirst(new StringBuffer().append(c));
            }else if(c>='a'&&c<='z'){
                char cc=q.peekFirst().charAt(0);
                if(cc>='a'&&cc<='z'||cc=='!'){
                    q.addFirst(q.pollFirst().append(c));
                }else{
                    q.addFirst(new StringBuffer().append(c));
                }
            }else if(c==']'){
                StringBuffer s1=q.pollFirst();
                StringBuffer res=new StringBuffer("");
                q.pollFirst();
                StringBuffer num=q.pollFirst();
                int len=num.length();
                for(int i=0;i<Long.valueOf(num.toString());i++){
                    res.append(s1);
                }
                if(q.peekFirst().charAt(0)!='[')
                    q.addFirst(q.pollFirst().append(res));
                else
                    q.addFirst(res);
            }
        }
        return q.pollFirst().toString().substring(1);
    }
}

739. 每日温度

一句话题意

        求序列后面比当前天温度高的最近的距离。

一句话题解

        单调递减栈。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> q = new LinkedList<>();
        int[] ans = new int[temperatures.length];
        Arrays.fill(ans,0);
        for(int i=0;i<temperatures.length;i++){
            if(q.size()==0||temperatures[q.peek()]>temperatures[i]){
                q.push(i);
            }else{
                while(q.size()>0&&temperatures[q.peek()]<temperatures[i]){
                    ans[q.peek()]=i-q.poll();
                }
                q.push(i);
            }
        }
        return ans;
    }
}

84. 柱状图中最大的矩形

一句话题意

        给定一个竖状图，求矩形最大面积。

一句话题解

        单调栈，设定一个单调递增的单调栈，然后每次扔值的时候，如果比前一个大正常往栈里扔，如果小的话就弹出栈内元素。且我们可以知道，当栈内某个元素作为高度，他后面的元素对于他来说都是有贡献的，我们只需要把这个算出来即可。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int ans = 0;
        Deque<Integer> q = new LinkedList<>();
        q.addFirst(-1);
        for (int i = 0; i <= n; i++) {
            int h;
            if(i==n) h=-1;
            else h=heights[i];
            while (q.size() > 1 && heights[q.peekFirst()] >= h) {
                int hh = heights[q.pollFirst()];
                int len = i - q.peekFirst() - 1;
                ans=Math.max(ans, hh * len);
            }
            q.addFirst(i);
        }
        return ans;
    }
}