largest-rectangle-in-histogram

gistfile1.txt

https://oj.leetcode.com/problems/largest-rectangle-in-histogram/

/*
O(n^2) : loop 두 개로 각 히스토그램마다 min, max를 이용해서 최대 크기를 구한다 : Time limit exceed

O(n) : O(n)알고리즘을 위해서는 index가 증가할때마다 실시간으로 계산하는 방식으로는 안됨 -> 계산 타이밍을 늦춰서 한꺼번에 계산할 수는 없을까? -> rectangle들을 저장해둘 extra space가 필요함 -> 순서를 기억하는 가장 적합한 자료구조인 stack 사용-> 오름차순으로 계속 스택에 저장하다가, top보다 작은 height[i]를 만나는 순간 미뤄왔던 계산 수행(while(s.top() > height[i]) -> 스택에는 항상 오름차순으로 유지.
while 루프가 끝난후, s.empty() == false이면 남은 rectangle 넓이 계산.

Time complexity : 
일반적인 경우, O(n)~ O(kn) 보장
최악의 경우, 처음부터 DESC로 정렬되어있는 input의 경우, 1칸 이동할때마다 i-1번 계산해야하므로, 1+2+3+... O(n^2)
좀 더 개선하기 위해서는 stack에 자료가 오름차순으로 저장되므로 vector와 binary search를 이용하면 안정적으로 최악 nlogn에 해결가능
*/

class Solution {
    public:
    int largestRectangleArea(vector<int> &height) {
        if(height.size() <= 0) return 0;
        
        int maxArea = -1;
        int i = 0;
        int area = 0;
        stack<int> stack;
        
        while(i < height.size()) {
           if(stack.empty() || height[stack.top()] <= height[i]) {
               stack.push(i++);
           } else {
               while(!stack.empty() && height[stack.top()] > height[i]) {
                   int topIndex = stack.top();
                   stack.pop();
                   
                   if(stack.empty()) {
                       area = height[topIndex]*i;
                   } else { //s.top()과 s.top()-1 번째 엘리먼트 사이에 있는 사각형들은 모두 s.top()보다 크므로 넓이계산시 포함시켜야 함
                       area = height[topIndex] * (i-stack.top()-1);  
                   }
                   
                   if(maxArea < area) maxArea = area;
               }
           }
        }
        
        while(!stack.empty()) {
            int topIndex = stack.top();
            stack.pop();
              
            if(stack.empty()) {
               area = height[topIndex]*i;
            } else {
                area = height[topIndex] * (i-stack.top()-1); 
            }
            
            if(maxArea < area) maxArea = area;
        }
         
        return maxArea;
    } 
    
};