We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Largest Rectangle
  2. Discussions

Largest Rectangle

Sort by

recency

|

25 Discussions

|

  • vdaons
     + 0 comments

    Python, recursive, not O(N) but short.

    def largestRectangle(h):
    if h:
        i = min(range(len(h)), key=h.__getitem__)
        return max(h[i] * len(h), largestRectangle(h[:i]), largestRectangle(h[i+1:]))
    return 0

  • cs_iot1b1550052
     + 0 comments

    def largestRectangle(h): # Write your code here stack = [0] area = 0 top = 0 h.append(0) for i in range(1, len(h)):

        if h[i] >= h[stack[-1]]:
        stack.append(i)

    else:
        while stack and h[i] < h[stack[-1]]:
            last = stack.pop()
            if stack:
                area = (i - stack[-1]-1) * h[last]
            else:
                area = i * h[last]
            if  area > top:
                top = area
        stack.append(i)

return top

  • vadym_usatiuk
     + 0 comments

    Java O(n)

    public static long largestRectangle(List<Integer> h) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;
        int n = h.size();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && h.get(stack.peek()) >= h.get(i)) {
                int height = h.get(stack.pop());
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, (long) height * width);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int height = h.get(stack.pop());
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, (long) height * width);
        }
        return maxArea;
    }

  • sagarbhatt_ons11
     + 0 comments

    Java 8 Solution: 

    public static long largestRectangle(List<Integer> h) {
                //1. Iterate the list of height. Set the max height of the building as first element.
                // then check the height difference to the adjacent building.
                // If the height is same or more, then go to next building.
                //Each time find the max rectangle and update the value.
                long maxRectangle = 0L;

                for(int i = 0; i < h.size(); i++){
                        int maxHt = h.get(i);
                        int maxlen = 1;
                        for(int j = i+1; j < h.size(); j++){
                                if(h.get(j) - h.get(j-1) < 0){
                                        if(maxHt > h.get(j))maxHt = h.get(j);
                                }
                                maxlen+= 1;
                                if(maxRectangle < maxHt*maxlen) maxRectangle = maxHt*maxlen;
                        }
                }
                return maxRectangle;
        }

  • arhamsoltani
     + 0 comments

    C#

    public static long largestRectangle(List<int> h) => 
        GetMaxArea(h, 0, h.Count()-1);
    
    private static long GetMaxArea(List<int> h, int l, int r) {
        if (l > r) return 0;
        if (l == r) return h[l];
        int min = int.MaxValue;
        int minIndex = -1;
        for (int i = l; i <= r; i++) {
            if (h[i] < min) {
                min = h[i];
                minIndex = i;
            }
        }
        long area = (r - l + 1) * min;
        long leftArea = GetMaxArea(h, l, minIndex-1);
        long rightArea = GetMaxArea(h, minIndex+1, r);
        return Math.Max(area, Math.Max(leftArea, rightArea));
    }