fork download
copy 
  1. /*
  2.  * ==========================================================
  3.  * All Patterns of Monotonic Deque / Stack in C++
  4.  * ==========================================================
  5.  * 1. Sliding Window Maximum
  6.  * 2. Sliding Window Minimum
  7.  * 3. Next Greater Element
  8.  * 4. Next Smaller Element
  9.  * 5. Previous Greater Element
  10.  * 6. Previous Smaller Element
  11.  * 7. Jump Game VI (DP + sliding window max)
  12.  * 8. Shortest Subarray with Sum at Least K
  13.  * 9. Constrained Subsequence Sum
  14.  * 10. Largest Rectangle in Histogram
  15.  * ==========================================================
  16.  */
  17.  
  18. #include <iostream>
  19. #include <deque>
  20. #include <vector>
  21. #include <climits>
  22. using namespace std;
  23.  
  24. // ----------------------------------------------------------
  25. // 1. Sliding Window Maximum
  26. //    Decreasing deque -> front is the max of the window
  27. // ----------------------------------------------------------
  28. vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  29.     deque<int> dq;  // stores indices
  30.     vector<int> res;
  31.     for (int i = 0; i < nums.size(); i++) {
  32.         // Remove index if it is outside the current window
  33.         if (!dq.empty() && dq.front() <= i - k)
  34.             dq.pop_front();
  35.  
  36.         // Remove from back all elements smaller than current
  37.         while (!dq.empty() && nums[dq.back()] < nums[i])
  38.             dq.pop_back();
  39.  
  40.         dq.push_back(i);
  41.  
  42.         // The front is the maximum for the current window
  43.         if (i >= k - 1)
  44.             res.push_back(nums[dq.front()]);
  45.     }
  46.     return res;
  47. }
  48.  
  49. // ----------------------------------------------------------
  50. // 2. Sliding Window Minimum
  51. //    Increasing deque -> front is the min of the window
  52. // ----------------------------------------------------------
  53. vector<int> minSlidingWindow(vector<int>& nums, int k) {
  54.     deque<int> dq;
  55.     vector<int> res;
  56.     for (int i = 0; i < nums.size(); i++) {
  57.         if (!dq.empty() && dq.front() <= i - k)
  58.             dq.pop_front();
  59.  
  60.         // Remove from back all elements larger than current
  61.         while (!dq.empty() && nums[dq.back()] > nums[i])
  62.             dq.pop_back();
  63.  
  64.         dq.push_back(i);
  65.  
  66.         if (i >= k - 1)
  67.             res.push_back(nums[dq.front()]);
  68.     }
  69.     return res;
  70. }
  71.  
  72. // ----------------------------------------------------------
  73. // 3. Next Greater Element (to the right)
  74. //    Monotonic decreasing stack (using deque as stack)
  75. // ----------------------------------------------------------
  76. vector<int> nextGreaterElement(vector<int>& nums) {
  77.     int n = nums.size();
  78.     vector<int> res(n, -1);
  79.     deque<int> st;  // stack of indices
  80.     for (int i = 0; i < n; i++) {
  81.         // While current is greater than top of stack, update answer
  82.         while (!st.empty() && nums[st.back()] < nums[i]) {
  83.             res[st.back()] = nums[i];
  84.             st.pop_back();
  85.         }
  86.         st.push_back(i);
  87.     }
  88.     return res;
  89. }
  90.  
  91. // ----------------------------------------------------------
  92. // 4. Next Smaller Element (to the right)
  93. //    Monotonic increasing stack
  94. // ----------------------------------------------------------
  95. vector<int> nextSmallerElement(vector<int>& nums) {
  96.     int n = nums.size();
  97.     vector<int> res(n, -1);
  98.     deque<int> st;
  99.     for (int i = 0; i < n; i++) {
  100.         // While current is smaller than top, update answer
  101.         while (!st.empty() && nums[st.back()] > nums[i]) {
  102.             res[st.back()] = nums[i];
  103.             st.pop_back();
  104.         }
  105.         st.push_back(i);
  106.     }
  107.     return res;
  108. }
  109.  
  110. // ----------------------------------------------------------
  111. // 5. Previous Greater Element (to the left)
  112. //    Monotonic decreasing stack (scan left to right)
  113. // ----------------------------------------------------------
  114. vector<int> previousGreaterElement(vector<int>& nums) {
  115.     int n = nums.size();
  116.     vector<int> res(n, -1);
  117.     deque<int> st;
  118.     for (int i = 0; i < n; i++) {
  119.         // Pop elements smaller than or equal to current
  120.         while (!st.empty() && nums[st.back()] <= nums[i])
  121.             st.pop_back();
  122.  
  123.         // Top is the previous greater (if exists)
  124.         if (!st.empty())
  125.             res[i] = nums[st.back()];
  126.  
  127.         st.push_back(i);
  128.     }
  129.     return res;
  130. }
  131.  
  132. // ----------------------------------------------------------
  133. // 6. Previous Smaller Element (to the left)
  134. //    Monotonic increasing stack
  135. // ----------------------------------------------------------
  136. vector<int> previousSmallerElement(vector<int>& nums) {
  137.     int n = nums.size();
  138.     vector<int> res(n, -1);
  139.     deque<int> st;
  140.     for (int i = 0; i < n; i++) {
  141.         // Pop elements larger than or equal to current
  142.         while (!st.empty() && nums[st.back()] >= nums[i])
  143.             st.pop_back();
  144.  
  145.         if (!st.empty())
  146.             res[i] = nums[st.back()];
  147.  
  148.         st.push_back(i);
  149.     }
  150.     return res;
  151. }
  152.  
  153. // ----------------------------------------------------------
  154. // 7. Jump Game VI (LeetCode 1696)
  155. //    You jump up to k steps, max sum from start to end.
  156. //    dp[i] = nums[i] + max(dp[i-1] ... dp[i-k])
  157. //    Use decreasing deque to keep max dp in window.
  158. // ----------------------------------------------------------
  159. int maxResult(vector<int>& nums, int k) {
  160.     int n = nums.size();
  161.     vector<int> dp(n);
  162.     dp[0] = nums[0];
  163.     deque<int> dq;
  164.     dq.push_back(0);
  165.  
  166.     for (int i = 1; i < n; i++) {
  167.         // Remove indices outside window of size k
  168.         if (dq.front() <= i - k)
  169.             dq.pop_front();
  170.  
  171.         // The max dp in the window is at the front
  172.         dp[i] = nums[i] + dp[dq.front()];
  173.  
  174.         // Maintain decreasing order of dp values
  175.         while (!dq.empty() && dp[dq.back()] <= dp[i])
  176.             dq.pop_back();
  177.  
  178.         dq.push_back(i);
  179.     }
  180.     return dp[n - 1];
  181. }
  182.  
  183. // ----------------------------------------------------------
  184. // 8. Shortest Subarray with Sum at Least K (LeetCode 862)
  185. //    Use prefix sums and an increasing deque.
  186. //    We want the smallest i < j with pref[j] - pref[i] >= k.
  187. // ----------------------------------------------------------
  188. int shortestSubarray(vector<int>& nums, int k) {
  189.     int n = nums.size();
  190.     vector<long long> pref(n + 1, 0);
  191.     for (int i = 0; i < n; i++)
  192.         pref[i + 1] = pref[i] + nums[i];
  193.  
  194.     deque<int> dq;
  195.     int minLen = n + 1;
  196.     for (int i = 0; i <= n; i++) {
  197.         // Try to shorten the subarray from the left
  198.         while (!dq.empty() && pref[i] - pref[dq.front()] >= k) {
  199.             minLen = min(minLen, i - dq.front());
  200.             dq.pop_front();
  201.         }
  202.  
  203.         // Keep deque increasing (by prefix sum)
  204.         while (!dq.empty() && pref[dq.back()] >= pref[i])
  205.             dq.pop_back();
  206.  
  207.         dq.push_back(i);
  208.     }
  209.     return (minLen == n + 1) ? -1 : minLen;
  210. }
  211.  
  212. // ----------------------------------------------------------
  213. // 9. Constrained Subsequence Sum (LeetCode 1425)
  214. //    Max sum of subsequence where |i - j| <= k.
  215. //    dp[i] = nums[i] + max(0, max(dp[i-k] ... dp[i-1]))
  216. //    Use decreasing deque to store dp values.
  217. // ----------------------------------------------------------
  218. int constrainedSubsetSum(vector<int>& nums, int k) {
  219.     int n = nums.size();
  220.     vector<int> dp(n);
  221.     deque<int> dq;
  222.     int ans = INT_MIN;
  223.     for (int i = 0; i < n; i++) {
  224.         // Max of previous window (or 0)
  225.         int best = dq.empty() ? 0 : dp[dq.front()];
  226.         dp[i] = nums[i] + max(0, best);
  227.         ans = max(ans, dp[i]);
  228.  
  229.         // Remove index out of window
  230.         if (!dq.empty() && dq.front() <= i - k)
  231.             dq.pop_front();
  232.  
  233.         // Maintain decreasing order of dp
  234.         while (!dq.empty() && dp[dq.back()] <= dp[i])
  235.             dq.pop_back();
  236.  
  237.         // Only push if dp[i] > 0 (optional but speeds up)
  238.         if (dp[i] > 0)
  239.             dq.push_back(i);
  240.     }
  241.     return ans;
  242. }
  243.  
  244. // ----------------------------------------------------------
  245. // 10. Largest Rectangle in Histogram (LeetCode 84)
  246. //     Monotonic increasing stack to find previous smaller
  247. //     and next smaller for each bar.
  248. // ----------------------------------------------------------
  249. int largestRectangleArea(vector<int>& heights) {
  250.     int n = heights.size();
  251.     deque<int> st;
  252.     int maxArea = 0;
  253.     for (int i = 0; i <= n; i++) {
  254.         int curHeight = (i == n) ? 0 : heights[i];
  255.         // Pop when a smaller height is encountered
  256.         while (!st.empty() && heights[st.back()] > curHeight) {
  257.             int h = heights[st.back()];
  258.             st.pop_back();
  259.             int width = st.empty() ? i : i - st.back() - 1;
  260.             maxArea = max(maxArea, h * width);
  261.         }
  262.         st.push_back(i);
  263.     }
  264.     return maxArea;
  265. }
  266.  
  267. // ----------------------------------------------------------
  268. // Example usage
  269. // ----------------------------------------------------------
  270. int main() {
  271.     vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
  272.     int k = 3;
  273.  
  274.     cout << "Sliding Window Maximum: ";
  275.     for (int x : maxSlidingWindow(nums, k)) cout << x << " ";
  276.     cout << endl;
  277.  
  278.     cout << "Sliding Window Minimum: ";
  279.     for (int x : minSlidingWindow(nums, k)) cout << x << " ";
  280.     cout << endl;
  281.  
  282.     vector<int> arr = {2, 1, 2, 4, 3};
  283.     cout << "Next Greater: ";
  284.     for (int x : nextGreaterElement(arr)) cout << x << " ";
  285.     cout << endl;
  286.  
  287.     cout << "Previous Smaller: ";
  288.     for (int x : previousSmallerElement(arr)) cout << x << " ";
  289.     cout << endl;
  290.  
  291.     vector<int> heights = {2, 1, 5, 6, 2, 3};
  292.     cout << "Largest Rectangle Area: " << largestRectangleArea(heights) << endl;
  293.  
  294.     return 0;
  295. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sliding Window Maximum: 3 3 5 5 6 7 
Sliding Window Minimum: -1 -3 -3 -3 3 3 
Next Greater: 4 2 4 -1 -1 
Previous Smaller: -1 -1 1 2 2 
Largest Rectangle Area: 10
https://ideone.com/4fmMVa
language:
C++ (gcc 8.3)
created:
13 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!