Jamzen的技术博客
0%

LeetCode.柱状图中最大的矩形

发表于 分类于 Valine：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

  • 示例:
    输入: [2,1,5,6,2,3]
    输出: 10

单调栈解法：

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
object LargestRectangleArea {

     def main(args: Array[String]): Unit = {
          println(largestRectangleArea(Array(0, 9)))
          println(largestRectangleArea(Array(2, 1, 5, 6, 2, 3)))

          println(largestRectangleArea2(Array(0, 9)))
          println(largestRectangleArea2(Array(2, 1, 5, 6, 2, 3)))

          println(largestRectangleArea3(Array(0, 9)))
          println(largestRectangleArea3(Array(2, 1, 5, 6, 2, 3)))
          println(largestRectangleArea3(Array(1, 2, 5, 6, 3, 2, 1, 6, 13)))
     }

     /**
      * 暴力解法,时间复杂度O(n^3)
      **/
     def largestRectangleArea(heights: Array[Int]): Int = {
          if (heights.length == 0) return 0
          var res = heights(0)
          for (i <- 0 until heights.length) {
               for (j <- i until heights.length) {
                    var min = Int.MaxValue
                    for (k <- i to j) {
                         if (heights(k) < min) {
                              min = heights(k)
                         }
                    }
                    val max = (j - i + 1) * min
                    if (max > res) {
                         res = max
                    }
               }
          }
          res
     }

     /**
      * 时间复杂度O(n^2)
      **/
     def largestRectangleArea2(heights: Array[Int]): Int = {
          if (heights.length == 0) return 0
          var res = heights(0)
          val dp = new Array[Array[Int]](heights.length)

          for (i <- 0 until heights.length) {
               dp(i) = new Array[Int](heights.length)
               dp(i)(i) = heights(i)
          }

          for (i <- 0 until heights.length) {
               for (j <- i until heights.length) {
                    if (i == j) dp(i)(j) = heights(j)
                    else {
                         dp(i)(j) = Math.min(dp(i)(j - 1), heights(j))
                    }
                    res = Math.max(dp(i)(j) * (j - i + 1), res)
               }
          }

          res
     }

     /**
      * [1, 2, 5, 6, 3, 2, 1, 6, 13, 0]
      *
      * [1] -> [1,2] -> [1,2,5] -> [1,2,5,6] -> [1,2,5] 6 * 1 -> [1,2] 5 * 2 -> [1,2,3] -> [1,2] 3 * 3 -> [1] 2 * 4 ->
      * [1,2] -> [1] 2 * 5 -> [] 1 * 6 -> [1] -> [1,6] -> [1,6,13] -> [1,6] 13 * 1 -> [1] 6 * 2 -> [] 1 * 9
      *
      * 单调栈，每个元素只入栈出栈一次，时间复杂度O(n)
      */
     def largestRectangleArea3(height: Array[Int]): Int = {
          if (height.length == 0) return 0

          var list: List[Int] = height.toList
          val heights = new ListBuffer[Int]()
          heights ++= list
          heights += 0

          var res = 0
          val st = new java.util.Stack[Int]()
          var i = 0

          while (i < heights.length) {
               if (st.isEmpty || heights(i) > heights(st.peek())) {
                    st.push(i)
                    i += 1
               } else {
                    val curr = st.peek()
                    st.pop()
                    val area = heights(curr) * (if (st.isEmpty()) i else (i - 1 - st.peek()))
                    res = Math.max(res, area)
               }
          }

          res
     }
}