Leetcode 84: Largest rectangle in histogram

April 5, 2018

Introduction

It is time for me to learn this hard level algorithm again. I know that it takes at least 10 practice for me to learn a hard level algorithm. Today I chose to study the video prepared by basketwangcoding in Chinese. My last practice was on January 18, 2018. Here is the blog.

30 minutes video lesson

I like to write down some notes from the lecture.

Brute force solution


In order to learn the algorithm very well this time, I like to work on the test case, [2, 4, 6, 5, 3], explain to myself how to solve the algorithm using O(n^2) brute force solution first.

How many rectangles to be calculated? What is the maximum rectangle area's value?


Iterate the end position from i = 0 to 4.

i = 0, the rectangle is 2.
i = 1, the rectangle is 4.
i = 2, the rectangle is 6.
i = 3, the rectangle is 5 + 5 = 10
i = 4, the rectangle is 3 + 3 + 3 + 3 = 12.

So the maximum rectangle is 12.

For each end index, we can go backward to search until the array's value is less than end index's value.

Or I also can think about the alternative idea. It is to iterate the start position from i = 0 to 4,

i = 0, the rectanlge is 2 + 2 + 2 + 2 + 2 = 10.
i = 1, the rectangle is 4 + 4 + 4 = 12.
i = 2, the rectangle is 6.
i = 3, the rectangle is 5
i = 4, the rectangle is 3