What is the best run-time for this problem?


  • 8
    C

    What is the best run-time for this problem?


  • 16
    N

  • 2
    H

    Here is my solution. It is AC and straightforward. There are steps to improve though. What do you think?

    public class Solution {
        int max = 0;
        int [] h;
        class WorkItem {
            int from, to, level;
            WorkItem(int from, int to, int level) {
                this.from = from; this.to = to; this.level = level;
            }
        }
        Deque<WorkItem> items = new LinkedList<>();
        
        public int largestRectangleArea(int[] height) {
            max = 0;
            if (height == null || height.length == 0) return 0;
            if (height.length == 1) return height[0];
            this.h = height;
            int level = 1;
            items.clear();
            for (int i = 0; i < height.length; i++) {
                level = Math.min(level, height[i]);
            }
            items.addLast(new WorkItem(0, height.length, level));
            WorkItem next;
            while ((next = items.pollFirst()) != null) {
                process(next.from, next.to, next.level);
            }
            return max;
        }
        
        private void process(int start, int end, int level) {
            if (start >= end) return;
            if (start == end - 1 && h[start] > 0) {
                max = Math.max(max, h[start]);
                return;
            }
            int nextLevel = Integer.MAX_VALUE;
            for (int i = start; i < end; i++) {
                if (h[i] < level) {
                    items.addLast(new WorkItem(start, i, level));
                    items.addLast(new WorkItem(i + 1, end, level));
                    return;
                } else {
                    if (h[i] > level) {
                        nextLevel = Math.min(nextLevel, h[i]);
                    }
                }
            }
            max = Math.max(max, level * (end - start));
            if (nextLevel > level && nextLevel <= Integer.MAX_VALUE) {
                items.addLast(new WorkItem(start, end, nextLevel));
            }
        }
    }

  • 2
    S
    According the GeeksForGeeks's idea, two different implementation, both are O(n) time complexity
    
    int largestRectangleArea(vector<int> &height) {
        // push a sentinel node back into the end of height
        // to make the code logic more concise
        height.push_back(0);
        stack<int> s;
        int ret = 0, h = 0, w = 0;
        int i = 0, n = height.size();
        
        while (i < n) {
            if (s.empty() || height[s.top()] <= height[i])
                s.push(i++);
            else {
                h = height[s.top()];
                s.pop();
                w = s.empty() ? i : i - s.top() - 1;
                if (h * w > ret) ret = h * w;
            }
        }
        
        return ret;
    }
    
    // all the nodes just push in and pop out once
    // time complexity is O(2n)
    int largestRectangleArea1(vector<int> &height) {
        int ret = 0;
        height.push_back(0);
        vector<int> index;
        
        int h = 0, w = 0;
        for(int i = 0; i < height.size(); i++) {
            while(index.size() > 0 && height[index.back()] >= height[i]) {
                h = height[index.back()];
                index.pop_back();
    
                w = index.size() > 0 ? i - index.back() - 1 : i;
                if(h * w > ret) ret = h * w;
            }
            
            index.push_back(i);
        }
    
        return ret;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.