Largest Rectangle in Histogram [C++]
IntuitionTo solve the problem of finding the largest rectangle area in a histogram, we need to consider how to efficiently calculate the area of the largest rec
# Intuition
To solve the problem of finding the largest rectangle area in a histogram, we need to consider how to efficiently calculate the area of the largest rectangle that can be formed within the bounds of the histogram. The key insight is to use a stack to keep track of the indices of the bars in the histogram, which allows us to calculate the area of rectangles in a systematic way.

# Approach
1. **Initialize a stack**: We use a stack to store the indices of the bars. This helps in keeping track of the bars that can form potential rectangles.
2. **Iterate through the bars**: We iterate through each bar in the histogram. For each bar, we check if it is smaller than the bar at the top of the stack.
3. **Calculate the area**: If the current bar is smaller, it means we have found the right boundary for the rectangle formed by the bar at the top of the stack. We then calculate the area of this rectangle and update the maximum area if this area is larger than the previously recorded maximum area.
4. **Push the current index to the stack**: After processing, we push the current index onto the stack.
5. **Handle remaining bars**: After processing all bars, we handle any remaining bars in the stack in a similar manner to ensure all possible rectangles are considered.

This approach ensures that we efficiently calculate the largest rectangle area by leveraging the stack to keep track of potential rectangles and their boundaries.

# Complexity
- **Time complexity**: The time complexity is \(O(n)\), where \(n\) is the number of bars in the histogram. This is because each bar is pushed and popped from the stack exactly once.
- **Space complexity**: The space complexity is \(O(n)\) due to the stack used to store the indices of the bars.

# Code
```cpp
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> s;
        int maxArea = 0;

        for (int i = 0; i <= n; ++i) {
            int h = (i == n) ? 0 : heights[i];
            while (!s.empty() && h < heights[s.top()]) {
                int height = heights[s.top()];
                s.pop();
                int width = s.empty() ? i : i - s.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            s.push(i);
        }
        return maxArea;
    }
};
```

### Explanation
- **Initialization**: We start by initializing a stack and a variable `maxArea` to keep track of the maximum area found.
- **Iteration**: We iterate through each bar in the histogram. For each bar, we check if it is smaller than the bar at the top of the stack.
- **Area Calculation**: If the current bar is smaller, we calculate the area of the rectangle formed by the bar at the top of the stack. The height of the rectangle is the height of the bar at the top of the stack, and the width is the distance between the current index and the index of the previous bar in the stack.
- **Update Maximum Area**: We update `maxArea` if the calculated area is larger than the current `maxArea`.
- **Push to Stack**: After processing, we push the current index onto the stack.
- **Final Processing**: After processing all bars, we handle any remaining bars in the stack to ensure all possible rectangles are considered.

This method ensures that we efficiently find the largest rectangle area in the histogram using a stack-based approach.
['C++']