Hello, everyone! Today I solved three LeetCode problems-Sum of Subarray Ranges, Largest Rectangle in Histogram, and Evaluate Reverse Polish Notation. All the problems mentioned above can be solved with the stack, and all the three problems have some unique logics along with the stack implementation.
Sum of Subarray Ranges is solvable both with the help of a stack and without using it. The latter part can be solved by means of brute force, the former way can be an optimization.
We use a stack that keeps track of the indices of the bars representing the minimum heights in order to solve Largest Rectangle in Histogram. Then we compute their areas using the obtained heights and calculate the area of maximum value to solve the problem efficiently.
The only way to solve the problem Evaluate Reverse Polish Notation is by using a stack. We push the digits onto the stack and pop them when we encounter operators, applying the operations according to the operator encountered and thereby evaluating the expression in the end.
In summing up the ranges of the subarrays, we used two stacks. One we are using to calculate the summation of minimums, the other to calculate the summation of maximums, and finally subtracting from the summation of the maximums the summation of the minimums we get the summation of the subarray ranges.
I hope my experience will be helpful!
Top comments (0)