devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode-hot100-栈_leetcode hot100在哪里

作者：Gausst松鼠会 | 2024-05-12 18:24:24

赞

踩

leetcode hot100在哪里

文章目录

20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：

  1. 使用map和stack结合.

  2. map中的key是右括号，value是左括号。

  3. stack中存放所有的左括号

    1. 扫描到当前字符时，看当前括号是左括号还是右括号
      1. 如果是右括号，那么就去map中查找，是否包括对应的左括号。
      2. 在找对应左括号的时候，如果此时栈为空或者栈顶不和当前右括号对应，那么说明是不匹配的，直接false。
      3. 如果匹配，就将左括号弹出栈。
    2. 不是就是遇见左括号，进栈。

  4. 最后只需要判断栈是否为空即可。

  • 代码

    class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n % 2 == 1){
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < n; i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                if(stack.isEmpty() || stack.peek() != map.get(c)){
                    return false;
                }else{
                    stack.pop();
                }
            }else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

32. 最长有效括号 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：

  1. 设置一个栈，先放入一个-1。保证是一个单调栈（主要是防止当第一个字符是")"进行pop的时候，出现空指针）。

  2. 依次扫描

    1. 如果扫描到当前为左括号，那么入栈。
    2. 如果扫描到当前为右括号，先出栈，所以预先放入一个-1，就是为了防止空指针异常。
    3. 如果此时栈为空，入栈。
    4. 如果此时栈中还有元素，那么此时全局变量为res 和 i - stack.peek()的最大值。

  3. 返回最大值。

  • 代码

    class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for(int i = 0; i < n; i++){
            char c = s.charAt(i);
            if(c == '('){
                stack.push(i);
            }else {
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

42. 接雨水 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：
  1. 设计一个栈，这个栈是一个单调递增的栈。因为是单调栈，所以保存的是下标。
  2. 因为题目的意思是按照长宽相乘进行解答的。
  3. 对给定的数组进行扫描
    1. 使用while判断，这样一直找到最远的那个墙（可以接雨水的），栈是否为空以及栈顶对应height数组的值是否大于现在扫描的height值。如果当前height值大于栈顶height值，那么说明出现了凹槽了，可以存放雨水。
      1. 弹出凹槽。
      2. 如果弹出之后为空，说明左边弹出完了，左边已经没有比现在更高的墙了。那么到此之后进栈顺序又要从当前的位置重新计算。
      3. 只要没有弹完，那么说明还有一个墙比当前位置高，记录下该墙的下标，即：栈顶。
      4. 每次弹出求一次宽度：i - left - 1，-1是因为弹出了一个凹槽，因为凹槽的宽度就是需要的宽度。
      5. 每次弹出计算一次长度：在当前height值和左边墙的height值选取一个最小值，然后再减去弹出的凹槽值，因为凹槽不一定是全没有的，可能是比较短的墙。
      6. 结果就是不断的进行长宽相乘再叠加。
  4. 返回值
  5. 为什么不需要设置-1这些给栈打底？32题打底的前提是可能首先面对的是右括号，所以要先打底一个-1。本题不需要打底是因为弹出的条件是当前height值高于栈顶的值，否则就入栈。潜台词就是：因为存在和栈顶的比较，那么肯定就有入栈的操作。
  6. 在求高度的时候，是当前墙的高度和左边墙高度的最小值减去凹槽的高度。

  • 代码

    class Solution {
    public int trap(int[] height) {
      int n = height.length;
      int res = 0;
      Deque<Integer> stack = new LinkedList<>();
      for(int i = 0; i < n; i++){
          while(!stack.isEmpty() && height[i] > height[stack.peek()]){
              //弹出凹槽部分（可能是空槽，也可能是矮墙）
              int top = stack.pop();
              if(stack.isEmpty()){
                  break;
              }
              int left = stack.peek();
              int widthNow = i - stack.peek() - 1;
              //高度为当前高度和左边墙的高度的最小值，再减去凹槽
              int heightNow = Math.min(height[i],height[left]) - height[top];
              res += widthNow * heightNow;
          }
          stack.push(i);
      }   
      return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

84. 柱状图中最大的矩形 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：
  1. 维护一个单调的栈，这个题只能是下标。
  2. 给柱子两边加一个0，为的就是为了维护一个单调性，防止栈空。
  3. 为什么要给两边加？加最左边是为了单调，那么加在最右边的目的是为了因为题目的弹出策略，只要当当前柱子的高度小于栈顶柱子的高度就弹出，那么加在最右边是为了计算最后一个柱子的高度形成的矩形面积，如果不加的话，那么就会忽略最后一个实际柱子形成的面积。
  4. 扫描从左到右。
  5. 只要当前扫描的柱子高度比栈顶的小，那么说明可以构建出一个面积，如果是当前柱子比栈顶的柱子高度还高，那么说明还有可能存在更高的，所以将更高的入栈，此处和42题不同，42题是将矮的入栈。
  6. 获取左边柱子。
  7. 高度取左边柱子的高度而不去当前柱子和左边柱子的最小值。只要后入栈的柱子高度比前面矮，那么就计算一次。
  8. 当前的宽度同样和雨水题一样，i - stack.peek() - 1
  9. 面积就是宽×高和原面积的最大值。
  10. 返回最大值

  • 代码：

    class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] temp = new int[heights.length + 2];
        System.arraycopy(heights, 0, temp, 1, heights.length);
        Deque<Integer> stack = new LinkedList<>();
        int res = 0;
        for(int i = 0; i < temp.length; i++){
        //判断条件是当前位置的高度小于栈顶的高度，记住是循环
            while(!stack.isEmpty() && temp[i] < temp[stack.peek()]){
                int left = stack.pop();
                //h选择左边的高度。
                int h = temp[left];
                int w = i - stack.peek() - 1;
                res = Math.max(res, w * h);
            }
            stack.push(i);
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

85. 最大矩形 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：
  1. 使用上一题的思路
  2. 把每列的高度求出之后，当前i，j为1就使得高度加1，否则就置0，使用上一题，求出最大矩形。
  3. 每次只需要比较一下是否是最大值即可。
  4. 注意空的判断。
    在这里插入图片描述

  • 代码：

    class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0){
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == '1'){
                    heights[j] += 1;
                }else {
                //因为题目要求只保留全为1的
                    heights[j] = 0;
                }
            }
            //每一行求一次
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;

    }
    public int largestRectangleArea(int[] heights){
        int[] temp = new int[heights.length + 2];
        System.arraycopy(heights, 0 ,temp, 1, heights.length);
        Deque<Integer> stack = new LinkedList<>();
        int res = 0;
        for(int i = 0; i < temp.length; i++){
            while(!stack.isEmpty() && temp[i] < temp[stack.peek()]){
                int left = stack.pop();
                int h = temp[left];
                int w = i - stack.peek() - 1;
                res = Math.max(res, w * h);
            }
            stack.push(i);
        }
        return res;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

155. 最小栈 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：
  1. 使用两个栈：数据栈、最小栈都是LinkedList的。
  2. 说一下push的时候，对于正常数据栈来说，给值就压栈，但是最小栈，要看栈顶值和当前值的大小关系，如果给定的值大于栈顶值，最小栈再压入一个栈顶值就好，否则就把当前值压入。
  3. 所以还是可以使用push和pop，这些都是List中自带的。

  • 代码：

    class MinStack {
    Deque<Integer> data;
    Deque<Integer> minData;
    /** initialize your data structure here. */
    public MinStack() {
        data = new LinkedList<>();
        minData = new LinkedList<>();
    }
    
    public void push(int val) {
        data.push(val);
        if(minData.isEmpty() || minData.peek() >= val){
            minData.push(val);
        }else {
            minData.push(minData.peek());
        }
    }
    
    public void pop() {
        data.pop();
        minData.pop();
    }
    
    public int top() {
        return data.peek();
    }
    
    public int getMin() {
        return minData.peek();
    }
}

/**
 * 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();
 */

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

394. 字符串解码 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：
  1. 使用两个栈，数据栈和字符串栈，分别用来保存待重复的数字以及每次重复的字符串。字符串栈就是做一个缓存的。
  2. 初始化一个num，用来记录每次要重复的数字，因为取出来的都是一个字符，要转成数字；以及要初始化一个用来保存更新的局部字符串的StringBuffer的变量。
  3. 对字符串进行判断：
    1. 如果当前扫描到的是数字，那么转换， num = num * 10 + (c - ‘0’); 可能之后还可能是一个数字，所以进行一个重复。
    2. 如果扫描到的是字符，那么直接添加到字符串sb中，做一个临时保存。
    3. 如果扫描到的是左括号，那么说明要对之间的字符串进行一个保存，方便后面出栈的时候拼接，即：将之前sb字符串保存到字符串栈中。每次只要向临时字符串栈添加了数据，就要将这个sb重新new，永远让sb保持一段缓存的字符串。再重新初始化这个临时的字符串sb，同时向数字栈保存之前计算出的要重复几次的数字。同样完成之后要重置。
    4. 如果当前扫描到的是右括号，那么先从数字栈中取出重复几次的数字。取出字符串栈栈顶的字符串，然后重新初始化一个StringBuffer()，这个的作用就是记录对字符串栈重复出的结果。
    5. 每次做一个局部更新，即：将sb=newStr，这样每次重复完成，局部就是去掉当前左右括号更新完成的。

  • 代码

    class Solution {
    public String decodeString(String s) {
        Deque<Integer> numStack = new LinkedList<>();
        Deque<String> strStack = new LinkedList<>();
        StringBuffer sb = new StringBuffer();
        int num = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                num = num * 10 + (c - '0');
            }else if(Character.isLetter(c)){
                sb.append(c);
            }else if(c == '['){
                strStack.push(sb.toString());
                sb = new StringBuffer();
                numStack.push(num);
                num = 0;
            }else if(c == ']'){
                int repeat = numStack.pop();
                StringBuffer newStr = new StringBuffer();
                newStr.append(strStack.pop());
                for(int j = 0; j < repeat; j++){
                    newStr.append(sb.toString());
                }
                sb = newStr;
            }
        }
        return sb.toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

581. 最短无序连续子数组 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：
  1. 先明白题目的意思，即：找到中间是无序数组的长度。
  2. 使用栈，栈保持单调，分别从两个方向进行，从左到右（保持递增）、从右到左（保持递减）。因为单调，所以栈中存的都是数组下标。
  3. 从左到右的时候，需要找到比栈顶数（前一个数）小的位置，那么，此时left是min(left,stack.pop())，只要是递增，一直入栈就好。
  4. 从右到左，需要找到比栈顶数（后一个）大的位置，那么此时的right是max(right,stack.pop())，只要是递减的，一直入栈。
  5. 最后在返回的时候，做判断，如果right>left，那么返回right - left + 1，否则说明就没有找到。所以在初始化的时候，left=n，right=0。

  • 代码：

    class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        int n = nums.length;
        int l = n;
        int r = 0;
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && nums[i] < nums[stack.peek()]){
                int newLeft = stack.pop();
                l = Math.min(l, newLeft);
            }
            stack.push(i);
        }
        stack.clear();
        for(int i = n - 1; i >= 0; i--){
            while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                int newRight = stack.pop();
                r = Math.max(r, newRight);
            }
            stack.push(i);
        }
        if(r > l){
            return r - l + 1; 
        }else {
            return 0;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

739. 每日温度 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：
  1. 单调栈保存下标，维护一个单调递减的数据栈。
  2. 设置一个结果数组，大小和给定的数组大小一样。
  3. 扫描数组，如果当当前温度值大于前一个温度值，即：出现增大的情况，那么获取上一个温度值的下标，即：直接pop（），那么在res数组中，该值就是res(idx) = i - idx。
  4. 举个例子：{73,72}，先开始73入栈，下标为0入栈，那么72＜72，那么出栈，即：这个时候要获取结果数组中73对应值，那么此时先要获取下标，下标就是stack.pop()，其实恰好就是前一个压栈的值，再计算结果数组中的值就是用i-idx即可。如果最大值之后
    就没有出现更大值，那么就使用数组的默认值即可。

  • 代码

    class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new LinkedList<>();
        int n = temperatures.length;
        int[] res = new int[n];
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                int index = stack.pop();
                res[index] = i - index;
            }
            stack.push(i);
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

  • 思路：
  1. 使用两个栈进行模拟，一个用来临时存储，一个用来真正实现队列的。
  2. 每次只要要获取元素或者查看栈顶元素，那么首先要看缓存栈中是否存在数据，如果有，就全部加入到队列中。
  3. 最后判断为空时，也要看两个栈是否都没有数据。

  • 代码：

    class MyQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack2.isEmpty() && stack1.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/560164
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号