Largest Rectangle in Histogram

## Problem Given an array of integers `heights` representing the histogram's bar heights where the width of each bar is 1, return the **area of the largest rectangle** in the histogram. ## Examples **Example 1:** ``` Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The largest rectangle spans bars at indices 2 and 3 (heights 5 and 6), giving area = 5 * 2 = 10. ``` **Example 2:** ``` Input: heights = [2,4] Output: 4 ``` **Example 3:** ``` Input: heights = [1] Output: 1 ``` ## Approach Hints Use a monotonic increasing stack. For each bar, when you encounter a bar shorter than the stack top, pop and calculate the area using the popped bar's height. The width extends from the new stack top to the current index. Append a sentinel value of 0 to flush the stack at the end.