0084 solved.

liuyubobobo · liuyubobobo · commit 0a4ecd17460b · 2020-05-14T00:14:29.000-07:00
diff --git a/0084-Largest-Rectangle-in-Histogram/cpp-0084/CMakeLists.txt b/0084-Largest-Rectangle-in-Histogram/cpp-0084/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.16)
+project(cpp_0084)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0084 main3.cpp)
diff --git a/0084-Largest-Rectangle-in-Histogram/cpp-0084/main.cpp b/0084-Largest-Rectangle-in-Histogram/cpp-0084/main.cpp
@@ -0,0 +1,96 @@
+/// Source : https://leetcode.com/problems/largest-rectangle-in-histogram/
+/// Author : liuyubobobo
+/// Time   : 2020-05-13
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Divide and Conquer + Segment Tree
+/// Time Complexity: O(nlogn)
+/// Space Complexity: O(n)
+class SegmentTree{
+
+private:
+    int n;
+    vector<int> data, tree;
+
+public:
+    SegmentTree(const vector<int>& data): data(data.begin(), data.end()), n(data.size()), tree(4*n, 0){
+        buildSegTree(0, 0, n - 1);
+    }
+
+    int query(int l, int r){
+        return query(0, 0, n - 1, l, r);
+    }
+
+private:
+    void buildSegTree(int treeID, int l, int r){
+
+        if(l == r){
+            tree[treeID] = l;
+            return;
+        }
+
+        int mid = (l + r) / 2;
+        buildSegTree(treeID * 2 + 1, l, mid);
+        buildSegTree(treeID * 2 + 2, mid + 1, r);
+        tree[treeID] = data[tree[treeID * 2 + 1]] < data[tree[treeID * 2 + 2]] ? tree[treeID * 2 + 1] : tree[treeID * 2 + 2];
+        return;
+    }
+
+    int query(int treeID, int l, int r, int ql, int qr){
+
+        if(ql == l && qr == r)
+            return tree[treeID];
+
+        int mid = (l + r) / 2;
+        if(qr <= mid) return query(treeID * 2 + 1, l, mid, ql, qr);
+        else if(ql > mid) return query(treeID * 2 + 2, mid + 1, r, ql, qr);
+
+        int resl = query(treeID * 2 + 1, l, mid, ql, mid);
+        int resr = query(treeID * 2 + 2, mid + 1, r, mid + 1, qr);
+        return data[resl] < data[resr] ? resl : resr;
+    }
+};
+
+class Solution {
+
+private:
+    int n;
+
+public:
+    int largestRectangleArea(vector<int>& heights) {
+
+        n = heights.size();
+        if(!n) return 0;
+
+        SegmentTree tree(heights);
+        return largest(heights, 0, n - 1, tree);
+    }
+
+private:
+    int largest(const vector<int>& heights, int l, int r, SegmentTree& tree){
+
+        if(l > r) return 0;
+        if(l == r) return heights[l];
+
+        int min_index = tree.query(l, r);
+        int res = largest(heights, l, min_index - 1, tree);
+        res = max(res, largest(heights, min_index + 1, r, tree));
+        res = max(res, heights[min_index] * (r - l + 1));
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<int> heights = {2,1,5,6,2,3};
+    cout << Solution().largestRectangleArea(heights) << endl;
+    // 10
+
+    return 0;
+}
diff --git a/0084-Largest-Rectangle-in-Histogram/cpp-0084/main2.cpp b/0084-Largest-Rectangle-in-Histogram/cpp-0084/main2.cpp
@@ -0,0 +1,79 @@
+/// Source : https://leetcode.com/problems/largest-rectangle-in-histogram/
+/// Author : liuyubobobo
+/// Time   : 2020-05-13
+
+#include <iostream>
+#include <vector>
+#include <stack>
+
+using namespace std;
+
+
+/// Monotone Stack
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+
+public:
+    int largestRectangleArea(vector<int>& heights) {
+
+        int n = heights.size();
+        if(!n) return 0;
+
+        stack<int> stack;
+        int res = 0;
+        for(int i = 0; i < n; i ++){
+            while(!stack.empty() && heights[i] < heights[stack.top()]){
+                int x = stack.top();
+                res = max(res, heights[x]);
+                stack.pop();
+                if(!stack.empty()) res = max(res, heights[x] * (i - 1 - (stack.top() + 1) + 1));
+                else res = max(res, heights[x] * i);
+            }
+            stack.push(i);
+        }
+
+        if(!stack.empty()){
+            int r = stack.top();
+            while(!stack.empty()){
+                int x = stack.top();
+                stack.pop();
+                res = max(res, heights[x]);
+
+                if(!stack.empty()) res = max(res, heights[x] * (r - (stack.top() + 1) + 1));
+                else res = max(res, heights[x] * n);
+            }
+        }
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<int> heights1 = {2,1,5,6,2,3};
+    cout << Solution().largestRectangleArea(heights1) << endl;
+    // 10
+
+    vector<int> heights2 = {2,1,2};
+    cout << Solution().largestRectangleArea(heights2) << endl;
+    // 3
+
+    vector<int> heights3 = {0, 9};
+    cout << Solution().largestRectangleArea(heights3) << endl;
+    // 9
+
+    vector<int> heights4 = {5, 4, 1, 2};
+    cout << Solution().largestRectangleArea(heights4) << endl;
+    // 8
+
+    vector<int> heights5 = {1, 2, 3, 4, 5};
+    cout << Solution().largestRectangleArea(heights5) << endl;
+    // 9
+
+    vector<int> heights6 = {4, 2, 0, 3, 2, 5};
+    cout << Solution().largestRectangleArea(heights6) << endl;
+    // 6
+
+    return 0;
+}
diff --git a/0084-Largest-Rectangle-in-Histogram/cpp-0084/main3.cpp b/0084-Largest-Rectangle-in-Histogram/cpp-0084/main3.cpp
@@ -0,0 +1,69 @@
+/// Source : https://leetcode.com/problems/largest-rectangle-in-histogram/
+/// Author : liuyubobobo
+/// Time   : 2020-05-14
+
+#include <iostream>
+#include <vector>
+#include <stack>
+
+using namespace std;
+
+
+/// Monotone Stack with sentinel to simplify the code
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+
+public:
+    int largestRectangleArea(vector<int>& heights) {
+
+        if(!heights.size()) return 0;
+
+        heights.insert(heights.begin(), 0);
+        heights.push_back(0);
+
+        stack<int> stack;
+        int res = 0;
+        for(int i = 0; i < heights.size(); i ++){
+            while(!stack.empty() && heights[i] < heights[stack.top()]){
+                int x = stack.top();
+                res = max(res, heights[x]);
+                stack.pop();
+                if(!stack.empty()) res = max(res, heights[x] * (i - 1 - (stack.top() + 1) + 1));
+                else res = max(res, heights[x] * i);
+            }
+            stack.push(i);
+        }
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<int> heights1 = {2,1,5,6,2,3};
+    cout << Solution().largestRectangleArea(heights1) << endl;
+    // 10
+
+    vector<int> heights2 = {2,1,2};
+    cout << Solution().largestRectangleArea(heights2) << endl;
+    // 3
+
+    vector<int> heights3 = {0, 9};
+    cout << Solution().largestRectangleArea(heights3) << endl;
+    // 9
+
+    vector<int> heights4 = {5, 4, 1, 2};
+    cout << Solution().largestRectangleArea(heights4) << endl;
+    // 8
+
+    vector<int> heights5 = {1, 2, 3, 4, 5};
+    cout << Solution().largestRectangleArea(heights5) << endl;
+    // 9
+
+    vector<int> heights6 = {4, 2, 0, 3, 2, 5};
+    cout << Solution().largestRectangleArea(heights6) << endl;
+    // 6
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -128,6 +128,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | | | | | | |
 | 082 | [Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) | [无] | [C++](0082-Remove-Duplicates-from-Sorted-List-II/cpp-0082/) | | |
 | 083 | [Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) | [无] | [C++](0083-Remove-Duplicates-from-Sorted-List/cpp-0083/) | | |
+| 084 | [Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/) | [solution](https://leetcode.com/problems/largest-rectangle-in-histogram/solution/) [题解](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode/) | [C++](0084-Largest-Rectangle-in-Histogram/cpp-0084/) | | |
 | | | | | | |
 | 086 | [Partition List](https://leetcode.com/problems/partition-list/description/) | [solution](https://leetcode.com/problems/partition-list/solution/) | [C++](0086-Partition-List/cpp-0086/) | | |
 | 087 | [Scramble String](https://leetcode.com/problems/scramble-string/description/) | [无] | [C++](0087-Scramble-String/cpp-0087/) | | |
