84. Largest Rectangle in Histogram

1.問題

• 給予n個整數代表長方形bar的高度, 找出最大面積的長方形

2.想法

• 提問

  • 確認題意: 將輸入的兩個字串轉為數字相乘並返回對應的字串

• function header, parameter

• test input

• 說明想法

  • 為了能夠保留最高的bar, 用stack存取: 當height[i] > stack.top時push, 反之開始計算最大面積

  • 最大面積有兩種情形

    • 1. stack.top到i - 1的面積 (不包含height[i])

      2. height[i]到stack.top的面積

      3. height[i]自己

  • 若stack內還有東西, 則計算stack內每個bar為基準時的面積

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) {
            return 0;
        }
        
        int n = heights.size(), area = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (i + 1 < heights.size() && heights[i] <= heights[i + 1]) {
                continue;
            }
            int minH = heights[i];
            for (int j = i; j >= 0; j--) {
                minH = min(minH, heights[j]);
                int tmpArea = minH * (i - j + 1);
                area = max(area, tmpArea);
            }
        }
        
        return area;
    }
};