剑指 Offer II 039. 直方图最大矩形面积

这道题挺坑人的。。 我其实刚开始没看懂意思= =
以为是求临近的两个柱子的最大面积= =。。

其实是求以某个柱子当作高度的时候。。 能形成的最大面积= =。。
找到某个柱子两边第一个小于当前柱子高度的柱子 然后 宽度就是right - left - 1
说实话 这个单调栈还是不太懂

func largestRectangleArea(_ heights: [Int]) -> Int {
      
      let len = heights.count
        if len == 1 {
            return heights[0]
        }
        
      var stack = Array<Int>()
        stack.append(-1)
      var area = 0
      for i in 0..<len {
      
          while (stack.last! != -1) && (heights[stack.last!] >=  heights[i]) {
              
              area = max(area, heights[stack.popLast()!] * (i - stack.last! - 1))
              
          }
          stack.append(i)
            
      }
        
        while stack.last! != -1 {
            
            area = max(area, heights[stack.popLast()!] * (len - stack.last! - 1))
            
        }
        
        
      return area
    
    }