Leetcode.84.Largest Rectangle in

题目

给定一个数组, 数组构成一个柱状图, 柱状图每个柱状高度为数组值, 宽度为1. 求柱状图中最大的矩形面积.

Input: [2,1,5,6,2,3]
Output: 10

思路1

循环嵌套, 简单粗暴.
时间复杂度O(n²)

 int largestRectangleArea(vector<int>& heights) {
    int n = (int)heights.size();
    int res = 0;
    for (int i = 0;i < heights.size();i++) {
        int minRec = heights[i];
        int minHeight = heights[i];
        for (int j = i-1;j >= 0 ;j--) {
            int width = i - j + 1;
            minHeight = min(minHeight, heights[j]);
            if (minHeight * width > minRec) {
                minRec = minHeight * width;
            }
        }
        res = max(res, minRec);
    }
    return res;
}

思路2

针对每个柱状图, 向左右寻找不比自己小的柱状.
时间复杂度O(n²/2)

int largestRectangleArea(vector<int>& heights) {
    int n = (int)heights.size();

    int res = 0;
    for (int i = 0; i < n; i++) {
        int h = heights[i];
        int l = i, r = i;
        while (l >= 0 && h <= heights[l]) l--;
        while (r < n && h <= heights[r]) r++;
        res = max(res, h * (r - l - 1));
    }
    return res;
}

思路3

使用栈, 当遇到比自己小的数就出栈, 遇到比自己大的数就入栈.

int largestRectangleArea(vector<int>& a) {
       int n = (int)a.size();
       int i = 0, maxarea = 0;
       stack<int> s;
       while(i<n) {
           if(s.empty()|| a[s.top()] <= a[i]) {
                s.push(i++);
           } else {
               int t = s.top();
               s.pop();
               int area = a[t] * (s.empty() ? i : i-s.top()-1);
               maxarea = max(maxarea,area);
           }
       }

       while(!s.empty()) {
           int t = s.top();
           cout << "t : " << t << endl;
           s.pop();
           int area =  a[t] * (s.empty() ? i : i-s.top()-1);
           maxarea = max(maxarea,area);
       }

       return maxarea;
    }

总结

从不同角度思考, 灵活运用各种数据结构.