275. H-Index II

Same as problem "274. H-Index".

1:  class Solution {  
2:  public:  
3:    int hIndex(vector<int>& citations) {  
4:      int h = 0, n = citations.size();  
5:      for (h = 0; h < n; h++) {  
6:        if (citations[h] >= n-h) break;  
7:      }  
8:      return n-h;  
9:    }  
10:  };  

84. Largest Rectangle in Histogram

The idea is to keep tracking the increasing rectangles (i.e. keep pushing increasing rectangles into stack) until one rectangle stops increasing (i.e. heights[i] <= heights[i-1]). At that point, we calculate the area. We'll pop out the rectangles that breaks the increasing sequence until a new increasing sequence including heights[i] is formed again. And then we'll start scanning next rectangle in the input again.
With regard to computing area, my initial thinking is the new area will be heights[stack.top] * (i - stack.top). However, this is wrong because this formula doesn't count the situation where the stack becomes empty. Note the stack keeps increasing rectangles so when it becomes empty, it means all the rectangle before the last one in the stack are higher than it. so the area should be heights[last stack element] * i.

1:  class Solution {  
2:  public:  
3:    int largestRectangleArea(vector<int>& heights) {  
4:      heights.push_back(0);  
5:      stack<int> stk;  
6:      int area = 0;  
7:      int height = 0, width = 0;  
8:      for (int i = 0; i < heights.size(); i++) {  
9:        while (!stk.empty() && heights[stk.top()] >= heights[i]) {  
10:          height = heights[stk.top()];  
11:          stk.pop();  
12:          width = stk.empty() ? i : i-stk.top()-1;  
13:          area = max(area, height*width);  
14:        }  
15:        stk.push(i);  
16:      }  
17:      return area;  
18:    }  
19:  };  

274. H-Index

I was thinking of scanning from the end and choose citations[i] if citations[i] >= n-i. However it turns out wrong. For example [100], the citation should be 1 instead of 100. The right way is to scan from the beginning and choose (n-i) as citation.

1:  class Solution {  
2:  public:  
3:    int hIndex(vector<int>& citations) {  
4:      sort(citations.begin(), citations.end());  
5:      int h = 0, n = citations.size();  
6:      for (int i = 0; i < n; i++) {  
7:        if (citations[i] >= n-i) {  
8:          h = n-i;  
9:          break;  
10:        }  
11:      }  
12:      return h;  
13:    }  
14:  };  

When I revisited this problem, I found a better explanation of the algorithm. If you sort the citations and put it into a graph, where x-axis represents the paper index and y-axis represents the citations. So, from the graph, the H-Index is length of the maximum square that in the histogram.