当前位置 博文首页 > Shockang的博客：LeetCode 刷题汇总之栈

最大化 缩小

    Shockang的博客：LeetCode 刷题汇总之栈

    作者：[db:作者] 时间：2021-08-23 22:09

    前言

    本文隶属于专栏《LeetCode 刷题汇总》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！

    本专栏目录结构请见LeetCode 刷题汇总

    正文

    20. 有效的括号

    看到括号，第一反应一定是栈

    Java 和 Scala 版本的栈推荐都使用 ArrayDeque，其中 Scala 也可以使用 ListBuffer，不过 ArrayDeque 的 API 更友好一点

    Java 版本

    class Solution {
    public boolean isValid(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(')
                stack.push(')');
            else if (c == '{')
                stack.push('}');
            else if (c == '[')
                stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c)
                return false;
        }
        return stack.isEmpty();
    }
}

    Scala 版本

    import java.util.ArrayDeque

object Solution {
  def isValid(s: String): Boolean = {
    val stack = new ArrayDeque[Char]()
    for (c <- s) {
      c match {
        case '(' => stack.push(')')
        case '[' => stack.push(']')
        case '{' => stack.push('}')
        case _ => if (stack.isEmpty || stack.pop() != c) return false
      }
    }
    stack.isEmpty
  }
}

    42. 接雨水

    接雨水这道题的思路：暴力解法（ O(n^2) ）-> 动态规划 3 次遍历（ O(n) ）-> 单调栈 1 次遍历（ O(n) ）-> 双指针 1 次遍历 （ O(n) ）

    选择单调栈是因为遍历过程中满足单调性（栈底到栈顶递减）
    接雨水中的凹槽口也很容易想到数学函数中的极小值，进而想到单调性 -> 单调栈

    Java 版本

    class Solution {
    public int trap(int[] height) {
        int n = height.length, res = 0;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        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 width = i - left - 1;
                // 对于凹槽口的底点来说，左右的较小值减去当前点的高度，即为雨水的高度
                int h = Math.min(height[i], height[left]) - height[top];
                res += width * h;
            }
            stack.push(i);
        }
        return res;
    }
}

    Scala 版本

    import java.util.ArrayDeque

import scala.util.control.Breaks._

object Solution {
  def trap(height: Array[Int]): Int = {
    if (height == null || height.isEmpty) return 0
    val stack = new ArrayDeque[Int]()
    var top, distance, boundedHeight, ans = 0
    for (current <- height.indices) {
      breakable(
        while (!stack.isEmpty && height(current) > height(stack.peek)) {
          top = stack.pop()
          if (stack.isEmpty) break
          distance = current - stack.peek() - 1
          boundedHeight = math.min(height(current), height(stack.peek())) - height(top)
          ans += distance * boundedHeight
        }
      )
      stack.push(current)
    }
    ans
  }
}

    71. 简化路径

    借助栈结构，然后在遍历的过程中对单点和双点特殊处理下

    Java 版本

    import java.util.StringJoiner;
class Solution {
    public String simplifyPath(String path) {
        String[] paths = path.split("/");
        ArrayDeque<String> stack = new ArrayDeque<>();
        for(String p: paths){
            if(!p.isEmpty() && !p.equals(".")){
                if(p.equals("..") && !stack.isEmpty()){
                    stack.pop();
                }else if(!p.equals("..")){
                    stack.push(p);
                }
            }
        }
        StringJoiner sj = new StringJoiner("/");
        // 这里我们借助 ArrayList 来逆序栈
        List<String> res = new ArrayList<>(stack);
        Collections.reverse(res);
        for(String s: res){
            sj.add(s);
        }
        return "/" + sj;
    }
}

    Scala 版本

    import scala.collection.mutable.ListBuffer

object Solution {
  def simplifyPath(path: String): String = {
    val paths = path.split("/")
    val res = ListBuffer[String]()
    for (p <- paths if p.nonEmpty && !p.equals(".")) {
      if (p.equals("..") && res.nonEmpty) res.remove(res.size - 1)
      else if (!p.equals("..")) res += p
    }
    "/" + res.mkString("/")
  }
}

    这里使用 ListBuffer 代码更简洁

    84. 柱状图中最大的矩形

    class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        ArrayDeque<Integer> s = new ArrayDeque<>();
        int maxArea = 0;
        for (int i = 0; i <= len; i++){
            int h = (i == len ? 0 : heights[i]);
            if (
    上一篇：Shockang的博客：为什么要有消息队列/消息引擎系统？
    下一篇：没有了