84. Largest Rectangle In Histogram
[!info] https://leetcode.com/problems/largest-rectangle-in-histogram/description/
#include <functional>#include <iostream>#include <print>#include <ranges>#include <stack>#include <vector>
namespace UsingStack { template<typename Compare> std::vector<int> computePreviousSmallerElement(std::ranges::constant_range auto&& arr, Compare&& cmp) { std::stack<int> stack; std::vector<int> prevElem; for (auto const& [idx, elem]: arr | std::views::enumerate) { while (!stack.empty() && cmp(elem, arr[stack.top()])) { stack.pop(); } auto prevElemIdx = stack.empty() ? -1 : stack.top(); prevElem.push_back(prevElemIdx); stack.push(idx); } return prevElem; }}
namespace UsingJumpPointers { template<typename Compare> std::vector<int> computePreviousSmallerElement(std::ranges::constant_range auto&& arr, Compare&& cmp) { std::vector<int> prevElem; for (auto const& [idx, elem]: arr | std::views::enumerate) { auto prevElemIdx = idx - 1; while (prevElemIdx != -1 && cmp(elem, arr[prevElemIdx])) { prevElemIdx = prevElem[prevElemIdx]; } prevElem.push_back(prevElemIdx); } return prevElem; }}
int largestRectangleInHistogram(std::vector<int> const& arr) { using namespace UsingJumpPointers;
auto leftSmallerElements = computePreviousSmallerElement(arr, std::less_equal<int>()); auto rightSmallerElements = computePreviousSmallerElement(arr | std::views::reverse, std::less_equal<int>()) | std::views::reverse | std::views::transform([size = static_cast<int>(arr.size())](auto const& reversedIdx) { return size - 1 - reversedIdx; }) | std::ranges::to<std::vector>();
int maxArea = 0; for (auto const& [idx, height]: arr | std::views::enumerate) { std::println("{} {} {}", leftSmallerElements[idx], idx, rightSmallerElements[idx]); auto width = rightSmallerElements[idx] - leftSmallerElements[idx] - 1; maxArea = std::max(maxArea, height * width); } return maxArea;}
int main() { auto area = largestRectangleInHistogram({2, 1, 5, 6, 2, 3}); std::println("largestRectangleInHistogram area: {}", area);}
Time complexity of UsingJumpPointers
is
Section titled “Time complexity of UsingJumpPointers is O(n)\mathcal{O}(n)O(n)”Intuition: In this part of the code,
while (prevElemIdx != -1 && cmp(elem, arr[prevElemIdx])) { prevElemIdx = prevElem[prevElemIdx];}
Imagine that prevElemIdx
disappears from the array after this while loop runs. Everything else would still work, and each element can disappear atmost once. So, time complexity must be