leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0084.cpp (836B)

0 class Solution { 1 public: 2 int largestRectangleArea(vector<int> &heights) { 3 int n = heights.size(); 4 vector<int> left(n), right(n); 5 stack<int> st; 6 7 for (int i = 0; i < n; i++) { 8 left[i] = i; 9 while (!st.empty() && heights[st.top()] >= heights[i]) { 10 left[i] = left[st.top()]; 11 st.pop(); 12 }; 13 st.push(i); 14 } 15 16 for (int i = n - 1; i >= 0; i--) { 17 right[i] = i; 18 while (!st.empty() && heights[st.top()] >= heights[i]) { 19 right[i] = right[st.top()]; 20 st.pop(); 21 }; 22 st.push(i); 23 } 24 25 int res = 0; 26 for (int i = 0; i < n; i++) 27 res = max(res, (right[i] - left[i] + 1) * heights[i]); 28 return res; 29 } 30 };