report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Histogram - MarisaOJ: Marisa Online Judge

Histogram

Time limit: 1000 ms
Memory limit: 256 MB
Find the biggest rectangle that can be formed in a given histogram using a series of adjacent bars with heights specified in an array. Assume all bars have the same width of 1 unit for simplicity. Visual representation for the sample test: ![](/media/media/ViYehcOKmRQ3v2M5eo200g.png) ### Input - The first line contains an integer $n$, the number of bars in the histogram. - The second line contains $n$ integers $h_i$, the bars height in the histogram, from left to right. ### Output - Print the maximum rectangle area. ### Constraints - $1 \le n \le 10^5$. - $1 \le A_i \le 10^9$. ### Example Input: ``` 6 2 1 5 6 2 3 ``` Output: ``` 10 ```
Monotonic queue
Nearest position
Subarray minimum
Peak Product
Histogram
Maximum subsequence value
Deleting digits
Electric poles
Planting flowers
Ring road
Prefix minimum
Knee surgery
Topic
Data structure
Rating 1500
Solution (0) Solution