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. Prepare
  2. Data Structures
  3. Stacks
  4. Largest Rectangle
  5. Discussions

Largest Rectangle

  • alkinemokiye
     + 0 comments

    took me 4 hours to do this, the logic is to find how much range that the number [i] can spread. spread is spread to max [index left] and to max [index right] starting from [i]. the valid range is when the number is higher than [i] number. i dont know if this acceptable since i dont use stack at all.

    public static long largestRectangle(List<Integer> h) {
		long result = Long.MIN_VALUE;
        
        for (int i = 0; i <= h.size() - 1; i++) {
            int left = i;
            int right = i;
            boolean goleft = true;
            boolean goright = true;
            
            while (goleft || goright) {
                int tempLeft = left - 1;
                if (tempLeft >= 0 && h.get(tempLeft) >= h.get(i)) {
                    left = tempLeft;
                } else {
                    goleft = false;
                }
                
                int tempRight = right + 1;
                if (tempRight <= h.size() - 1 && h.get(tempRight) >= h.get(i)) {
                    right = tempRight;
                } else {
                    goright = false;
                }
            }
            
            long tempResult = h.get(i) * (right - left + 1);
            if (result < tempResult) {
                result = tempResult;
            }
        }
    
        return result;
}