84. Largest Rectangle in Histogram

Hard (Khó) C++ Python 🔗 Xem trên LeetCode

📋 Đề Bài

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

 

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

 

Constraints:

  • 1 <= heights.length <= 105
  • 0 <= heights[i] <= 104

🧠 Thuật Toán & Kỹ Thuật

Binary Search (Tìm kiếm nhị phân)Stack (Ngăn xếp)
⏱️ Thời gian O(log n)
💾 Không gian O(n)

💻 Lời Giải

C++ 0084-largest-rectangle-in-histogram.cpp 
class SegmentTree {
private:
    vector<int> tree, heights;
    int n;
    
public:
    SegmentTree() {
        
    }
    
    SegmentTree(vector<int> heights) {
        this->heights = heights;
        this->n = heights.size();
        tree.resize(4*n);
        for (int i = 0; i < n; ++i) {
            update(1, 0, n - 1, i);
        }
    }
    
    void update(int node, int left, int right, int index) {
        if (index < left or index > right) {
            return;
        }
        if (left == right) {
            tree[node] = index;
            return;
        }
        int mid = (left + right) / 2;
        update(node*2, left, mid, index);
        update(node*2 + 1, mid + 1, right, index);
        if (heights[tree[node*2]] < heights[tree[node*2 + 1]]) {
            tree[node] = tree[node*2];
        }
        else {
            tree[node] = tree[node*2 + 1];
        }
    }
    
    int get_node(int node, int left, int right, int q_left, int q_right) {
        if (q_right < left or right < q_left) {
            return -1;
        }
        if (q_left <= left and right <= q_right) {
            return tree[node];
        }
        int mid = (left + right) / 2;
        int left_node = get_node(node*2, left, mid, q_left, q_right);
        int right_node = get_node(node*2 + 1, mid + 1, right, q_left, q_right);
        if (left_node == -1) {
            return right_node;
        }
        if (right_node == -1) {
            return left_node;
        }
        if (heights[left_node] < heights[right_node]) {
            return left_node;
        }
        else {
            return right_node;
        }
    }
    
    int get_node(int q_left, int q_right) {
        return get_node(1, 0, n - 1, q_left, q_right);
    }
};

class Solution {
private:
    vector<int> heights;
    SegmentTree st;
    
public:
    int rec(int left, int right) {
        if (right < left) {
            return 0;
        }
        int mid = st.get_node(left, right);
        return max({
            heights[mid] * (right - left + 1),
            rec(left, mid - 1),
            rec(mid + 1, right)
        });
    }
    
    int largestRectangleArea(vector<int>& heights) {
        this->heights = heights;
        SegmentTree st(heights);
        this->st = st;
        return rec(0, heights.size() - 1);
    }
};
Python 0084-largest-rectangle-in-histogram.py 
class Solution:
    def largestRectangleArea(self, nums: List[int]) -> int:
        n = len(nums)
        stack = []
        prefMinIndex = [-1] * n
        
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            if stack:
                prefMinIndex[i] = stack[-1]
            stack.append(i)
            
        stack = []
        suffMinIndex = [n] * n
        
        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            if stack:
                suffMinIndex[i] = stack[-1]
            stack.append(i)
            
        ans = 0
            
        for i in range(n):
            l = prefMinIndex[i] + 1
            r = suffMinIndex[i] - 1
            
            ans = max(ans, nums[i] * (r - l + 1))
        
        return ans