Histograms and daily temperatures

Questions 1 to 5 of 8

1. 1. What does this program print? ``cpp #include <cstddef> #include <iostream> #include <stack> #include <vector> std::vector<int> daily_temperatures(const std::vector<int>& temp) { std::vector<int> answer(temp.size(), 0); std::stack<std::size_t> waiting; for (std::size_t day = 0; day < temp.size(); ++day) { while (!waiting.empty() && temp[waiting.top()] < temp[day]) { std::size_t cold = waiting.top(); waiting.pop(); answer[cold] = static_cast<int>(day - cold); } waiting.push(day); } return answer; } int main() { auto ans = daily_temperatures({30, 20, 25, 28, 26, 31}); for (std::size_t i = 0; i < ans.size(); ++i) std::cout << (i ? " " : "") << ans[i]; std::cout << '\n'; } ``

   5 1 1 1 1 05 2 1 2 1 05 1 1 2 1 05 1 1 2 0 0
2. 2. What does this program print? ``cpp #include <algorithm> #include <cstddef> #include <iostream> #include <stack> #include <vector> long long largest_rectangle(const std::vector<int>& heights) { const int n = static_cast<int>(heights.size()); std::stack<int> waiting; long long best = 0; for (int i = 0; i <= n; ++i) { const int h = (i == n) ? 0 : heights[i]; while (!waiting.empty() && heights[waiting.top()] >= h) { const int bar = waiting.top(); waiting.pop(); const int left = waiting.empty() ? -1 : waiting.top(); const int width = i - left - 1; best = std::max(best, static_cast<long long>(heights[bar]) * width); } if (i < n) { waiting.push(i); } } return best; } int main() { std::cout << largest_rectangle({6, 2, 5, 4, 5, 1, 6}) << '\n'; } ``

   1012149
3. 3. The stack version of daily_temperatures is O(n), even though a while loop sits inside the for loop. Why?

   The while loop only runs on the first day, so the total is one passThe stack never holds more than eight days, so every loop is bounded by a constantEach answer is found with a binary search, which costs about log n per dayEach day is pushed once and popped at most once, so all the pops together are at most n
4. 4. The largest-rectangle stack method runs on a row of 6 bars, followed by the extra bar of height 0 that flushes the stack. How many times in total is pop() called on the stack?

   Type a number.

5. 5. In the largest-rectangle method, a bar's area is computed when the bar is popped, not when it is pushed. Why?

   Its height is only known once it is poppedThe area is too large to store until the stack is emptyIts right limit is not known until a shorter or equal bar arrives, and its left limit is the bar below it on the stack, so both limits are known only at the popPopping sorts the bars so the widths can be added