[OJ.leetcode] largest-rectangle-in-histogram

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

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

 /* 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; } };