Topic: Daily Temperature
-
Given an integer array
temperatures, representing the daily temperature, return an arrayanswer, whereanswer[i]refers to the temperature for the firstidays, with the next higher temperature occurring a few days later. If the temperature is not going to rise after this, use0instead. -
Brute force solution, two levels of for loop, to update the result array
-
class Solution { public: vector<int> dailyTemperatures(vector<int> & amp; temperatures) { vector<int> res(temperatures.size()); for(int i=0;i<temperatures.size();i + + ){ int dis=0; bool flag=true; for(int j=i + 1;j<temperatures.size();j + + ){ if(temperatures[i]>=temperatures[j]){ dis++; }else{ dis++; flag = false; break; } } if(flag){ dis=0; } res[i] = dis; } return res; } };//time out
-
-
For each element temperatures[i] in the temperature list, we need to find the smallest subscript j such that i < j and temperatures[i] < temperatures[j]. Since the temperature range is within [30, 100], you can maintain an array next to record the index of the first occurrence of each temperature. The elements in the array next are initialized to infinity, and the value of next is updated during the iteration of the temperature list.
-
Traverse the temperature list in reverse order. For each element temperatures[i], find the index of the first occurrence of each temperature from temperatures[i] + 1 to 100 in the array next, mark the smallest index among them as warmerIndex, then warmerIndex is the next temperature A higher bid than the current day. If warmerIndex is not infinite, warmerIndex – i is the number of waiting days until the next temperature is higher than the current day, and finally let next[temperatures[i]] = i.
-
class Solution { public: vector<int> dailyTemperatures(vector<int> & amp; temperatures) { int n=temperatures.size(); vector<int> ans(n),next(101,INT_MAX); for(int i=n-1;i>=0;i--){ int index=INT_MAX; for(int t = temperatures[i] + 1;t<=100; + + t){ index = min(index,next[t]); } if(index!=INT_MAX){ ans[i]=index-i; } next[temperatures[i]]=i; } return ans; } }; -
Time complexity: O(nm)), where n is the length of the temperature list, m is the length of the array next, in this question the temperature does not exceed 100, so the value of m is 100. Traverse the temperature list in reverse direction. For each value in the temperature list, traverse the array next. Space complexity: O(m), where m is the length of the array next. In addition to the return value, an array next of length m needs to be maintained to record the subscript position of the first occurrence of each temperature.
-
It is usually a one-dimensional array. To find the position of the first element on the right or left of any element that is larger or smaller than itself, at this time we will think of using a monotonic stack. The time complexity is O(n). The essence of a monotonic stack is to trade space for time, because during the traversal process, a stack is needed to record the first element on the right that is higher than the current element. The advantage is that the entire array only needs to be traversed once. To put it more straightforwardly, we use a stack to record the elements we have traversed, because when we traverse the array, we don’t know which elements we have traversed before, so we can’t find an element after traversing it. Have we traversed a smaller one before, so we need to use a container (a monotonic stack here) to record the elements we have traversed.
- What elements are stored in a monotonic stack? The monotonic stack only needs to store the subscript i of the element. If you need to use the corresponding element, you can get it directly from T[i].
- Are the elements in the monotonic stack increasing? Or is it decreasing? Here we need to use increasing order (again, the order from the top of the stack to the bottom of the stack), because only when incrementing, when an element i is added to the stack, do we know that the top element of the stack is the first on the right in the array The element larger than the top element of the stack is i. That is: if you find the first larger element to the right of an element, the monotonic stack is increasing; if you find the first smaller element to the right of an element, the monotonic stack is decreasing.
-
class Solution {<!-- --> public: vector<int> dailyTemperatures(vector<int> & amp; temperatures) {<!-- --> stack<int> st; vector<int> res(temperatures.size(),0); st.push(0);//0 means subscript for(int i=1;i<temperatures.size();i + + ){<!-- --> if(temperatures[i]<temperatures[st.top()]){<!-- --> st.push(i); }else if(temperatures[i]==temperatures[st.top()]){<!-- --> st.push(i); }else{<!-- --> while(!st.empty() & amp; & amp; temperatures[i] > temperatures[st.top()]){<!-- --> res[st.top()] = i-st.top(); st.pop(); } st.push(i); } } return res; } }; -
Time complexity: O(n); Space complexity: O(n)
Title: The next larger element I
-
The next greater element of the number
xinnums1meansxinnums2The first element on the right side of the corresponding position is larger thanx. You are given two arraysnums1andnums2with no duplicate elements. The subscripts start counting from 0, wherenums1is a subset ofnums2. For each0 <= i < nums1.length, find the subscriptjsuch thatnums1[i] == nums2[j], and determine the next larger element ofnums2[j]innums2. If there is no next larger element, the answer to this query is-1. Returns an arrayansof lengthnums1.lengthas the answer, such thatans[i]is as described aboveNext update Big Elements. -
Brutal solution, two-layer for loop
-
class Solution { public: vector<int> nextGreaterElement(vector<int> & nums1, vector<int> & nums2) { vector<int> res(nums1.size(),-1); for(int i=0;i<nums1.size();i + + ){ bool flag = false; for(int j=0;j<nums2.size();j + + ){ if(nums1[i]==nums2[j]){ flag = true; } if(flag & amp; & amp; nums1[i]<nums2[j]){ res[i] = nums2[j]; break; } } } return res; } };
-
-
From the question example, we can see that in the end, each element of nums1 is required to be the next element in nums2 that is larger than the current element, so it is necessary to define an array result with the same size as nums1 to store the result. The question says that if there is no corresponding position, -1 will be output. Therefore, if a certain position in the result array is not assigned a value, it should be -1, so it is initialized to -1.
-
In the process of traversing nums2, we need to determine whether nums2[i] has appeared in nums1, because in the end we need to update the result array based on the subscript of the nums1 element. Without repeated elements, we can use map for mapping. Quickly find the subscript based on the value, and you can also determine whether nums2[i] appears in nums1.
-
The order from the top of the stack to the bottom of the stack should be from small to large, that is, the elements in the stack should be kept in increasing order. As long as you keep incrementing, you can find the first element on the right that is larger than yourself. Next, we will analyze the following three situations, which must be analyzed clearly.
- Case 1: The currently traversed element T[i] is smaller than the top element T[st.top()] of the stack; at this time, the incremental stack (the order from the top of the stack to the bottom of the stack) is satisfied, so it is pushed directly onto the stack.
- Case 2: The currently traversed element T[i] is equal to the top element of the stack T[st.top()];
- Situation 3: The currently traversed element T[i] is greater than the top element T[st.top()] of the stack: If pushed onto the stack at this time, the incremental stack will not be satisfied. This is also to find the first element on the right that is larger than itself. when. Determine whether the element at the top of the stack has appeared in nums1 (note that the elements in the stack are elements of nums2). If it has appeared, start recording the result.
-
class Solution { public: vector<int> nextGreaterElement(vector<int> & nums1, vector<int> & nums2) { stack<int> st; vector<int> res(nums1.size(),-1); if(nums1.size()==0){ return res; } unordered_map<int,int> umap;// key: subscript element, value: subscript for(int i=0;i<nums1.size();i + + ){ umap[nums1[i]]=i; } st.push(0); for(int i=1;i<nums2.size();i + + ){ if(nums2[i]<nums2[st.top()]){ st.push(i); }else if(nums2[i] == nums2[st.top()]){ st.push(i); }else{ while(!st.empty() & amp; & amp; nums2[i] > nums2[st.top()]){ if(umap.count(nums2[st.top()])>0){ int index = umap[nums2[st.top()]]; res[index] = nums2[i]; } st.pop(); } st.push(i); } } return res; } };
Title: The Next Bigger Element II
-
Given a circular array
nums(the next element ofnums[nums.length - 1]isnums[0]), return The next larger element for each element innums. The next greater element of the numberxis the first greater number after this number in array traversal order, which means you should loop Search for its next larger number. If it does not exist,-1is output. -
Just splice the two arrays together and then use a monotonic stack to find the next maximum value! It does work!
-
class Solution {<!-- --> public: vector<int> nextGreaterElements(vector<int> & amp; nums) {<!-- --> vector<int> nums1(nums.begin(),nums.end()); nums.insert(nums.end(),nums1.begin(),nums1.end()); vector<int> res(nums.size(),-1); if(nums.size()==0){<!-- --> return res; } stack<int> st; st.push(0); for(int i=1;i<nums.size();i + + ){<!-- --> if(nums[i]<nums[st.top()]){<!-- --> st.push(i); }else if(nums[i]==nums[st.top()]){<!-- --> st.push(i); }else{<!-- --> while(!st.empty() & amp; & amp; nums[i] > nums[st.top()]){<!-- --> res[st.top()] = nums[i]; st.pop(); } st.push(i); } } res.resize(nums.size()/2); return res; } }; -
This way of writing is indeed more intuitive, but it does a lot of useless operations, such as modifying the nums array, and finally resizing the result array back. Resize is time-consuming and is an O(1) operation, but expanding the nums array is equivalent to an additional O(n) operation.
-
class Solution { public: vector<int> nextGreaterElements(vector<int> & nums) { int len = nums.size(); vector<int> res(len,-1); if(len==0){ return res; } stack<int> st; st.push(0); for(int i=1;i<len*2;i + + ){ if(nums[i % len] < nums[st.top()]){ st.push(i%len); }else if(nums[i%len] == nums[st.top()]){ st.push(i%len); }else{ while(!st.empty() & amp; & amp; nums[i%len]>nums[st.top()]){ res[st.top()]=nums[i%len]; st.pop(); } st.push(i%len); } } return res; } };
-
Topic: Catching rainwater
-
Given
nnon-negative integers representing the height map of each column with width1, calculate how much rainwater the columns arranged in this way can catch after it rains. -
The violent solution to this problem also uses double pointers. First of all, it is necessary to clarify whether to calculate according to rows or columns.
-
First of all, if calculated by columns, the width must be 1. We can then find the height of the rainwater in each column. **It can be seen that the height of each column of rainwater depends on the height of the tallest column on the left of the column and the height of the shortest column among the tallest columns on the right.
-
class Solution {<!-- --> public: int trap(vector<int> & amp; height) {<!-- --> int sum=0; for(int i=0;i<height.size();i + + ){<!-- --> if(i==0 || i==height.size()-1){<!-- --> continue; } int rH=height[i]; int lH= height[i]; for(int r=i + 1;r<height.size();r + + ){<!-- --> if(height[r]>rH){<!-- --> rH = height[r]; } } for(int l=i-1;l>=0;l--){<!-- --> if(height[l]>lH){<!-- --> lH = height[l]; } } int h=min(rH,lH) - height[i]; if(h>0){<!-- --> sum + =h*1; } } return sum; } };//time out -
Because every time you traverse a column, you have to look for the highest column on both sides, so the time complexity is O(n^2) and the space complexity is O(1). The double pointer method can be optimized
-
class Solution { public: int trap(vector<int> & amp; height) { if(height.size()<=2){ return 0; } vector<int> maxleft(height.size(),0); vector<int> maxright(height.size(),0); int size=maxright.size(); maxleft[0] = height[0]; for(int i=1;i<size;i + + ){// Record the maximum height of the left column of each column maxleft[i]=max(height[i],maxleft[i-1]); } maxright[size-1]=height[size-1]; for(int i=size-2;i>=0;i--){// Record the maximum height of the right column of each column maxright[i]=max(maxright[i + 1],height[i]); } int sum=0; for(int i=0;i<size;i + + ){ int count=min(maxleft[i],maxright[i])-height[i]; if(count>0){ sum + =count; } } return sum; } };
-
-
It is usually a one-dimensional array. To find the position of the first element on the right or left of any element that is larger or smaller than itself, at this time we will think of using a monotonic stack. As for the question of collecting rainwater, we need to find an element, the largest element on the right and the largest element on the left, to calculate the rainwater area.
-
First, the monotonic stack calculates rain according to the row direction, using the order of elements in the monotonic stack. The order from the stack head (elements are popped from the stack head) to the bottom of the stack should be from small to large. Because once it is found that the height of the added column is greater than the stack head element, a groove will appear. The stack head element is the column at the bottom of the groove, the second element of the stack head is the column on the left side of the groove, and the added element is the concave The pillar to the right of the slot.
-
When encountering the same element, updating the subscript in the stack means popping the element (old subscript) from the stack and adding the new element (new subscript) to the stack.
-
What values should be stored in the stack: Using a monotonic stack, the rainwater area is also calculated by length * width. The length is calculated by the height of the columns, and the width is calculated by the subscripts between the columns. So is it necessary to store an element of type pair
-
class Solution { public: int trap(vector<int> & amp; height) { if(height.size()<=2){ return 0; } stack<int> st; st.push(0); int sum=0; for(int i=1;i<height.size();i + + ){ if(height[i]<height[st.top()]){ st.push(i); }else if(height[i] == height[st.top()]){ st.push(i); }else{ while(!st.empty() & amp; & amp; height[i] > height[st.top()]){ int mid=st.top(); st.pop(); if(!st.empty()){ int h=min(height[st.top()],height[i])-height[mid]; int w=i-st.top()-1; sum + = h*w; } } st.push(i); } } return sum; } };
-
-
At this point, you should be able to find that it is actually the top of the stack, the next element on the top of the stack, and the element to be pushed onto the stack. Three elements to catch the water! **Then the height of the rainwater is min (height of the left side of the groove, height of the right side of the groove) - height of the bottom of the groove, the code is:
int h = min(height[st.top()], height[i]) - height[mid];The width of rainwater is the subscript on the right side of the groove - the subscript on the left side of the groove - 1 (because only the middle width is found), the code is:int w = i - st.top () - 1 ;The volume of rainwater in the current groove is:h * w.
Title: The largest rectangle in the histogram
-
Given n non-negative integers, used to represent the height of each column in the histogram. Each column is adjacent to each other and has width 1 . Find the maximum area of the rectangle that can be drawn in this histogram.
-
Violent solution, timeout
-
class Solution {<!-- --> public: int largestRectangleArea(vector<int> & amp; heights) {<!-- --> int sum=0; for(int i=0;i<heights.size();i + + ){<!-- --> int left=i; int right=i; for(;left>=0;left--){<!-- --> if(heights[left]<heights[i]){<!-- --> break; } } for(;right<heights.size();right + + ){<!-- --> if(heights[right]<heights[i]){<!-- --> break; } } int w=right-left-1; int h=heights[i]; sum=max(sum,h*w); } return sum; } };
-
-
In this question, you need to record the subscript of the first left column that is smaller than the column, rather than the height of the first left column that is smaller than the column.
-
class Solution { public: int largestRectangleArea(vector<int> & heights) { int len = heights.size(); vector<int> minleft(len); vector<int> minright(len); //Record the first subscript on the left of each column that is smaller than the column minleft[0]=-1; for(int i=1;i<len;i + + ){ int t=i-1; while(t>=0 & amp; & amp; heights[t]>=heights[i]){ t = minleft[t]; } minleft[i] = t; } minright[len-1]=len; for(int i=len-2;i>=0;i--){ int t=i + 1; while(t<len & amp; & amp; heights[t]>=heights[i]){ t = minright[t]; } minright[i]=t; } int res=0; for(int i=0;i<len;i + + ){ int sum = heights[i]*(minright[i]-minleft[i]-1); res = max(res,sum); } return res; } };
-
-
This involves a very important property of the monotonic stack, which is the order in the monotonic stack, whether from small to large or from large to small. Because this question is to find the first column on the left and right sides of each column that is smaller than the column, so the order from the top of the stack (the elements are popped from the top of the stack) to the bottom of the stack should be from large to small!
-
Only in order from large to small in the stack can we ensure that the top element of the stack finds the first pillar on the left and right sides that is smaller than the top element of the stack. At this point, you should be able to find that it is actually the top of the stack, the next element on the top of the stack, and the three elements to be pushed into the stack that form the height and width of the maximum area we require. The main thing is to analyze clearly the following three situations:
- Case 1: The currently traversed element heights[i] is greater than the top element heights[st.top()] of the stack
- Case 2: The currently traversed element heights[i] is equal to the top element heights[st.top()] of the stack
- Case 3: The currently traversed element heights[i] is less than the top element heights[st.top()] of the stack
-
class Solution { public: int largestRectangleArea(vector<int> & heights) { int res=0; stack<int> st; heights.insert(heights.begin(),0);//Add element 0 to the head of the array heights.push_back(0); st.push(0); for(int i=1;i<heights.size();i + + ){ if(heights[i]>heights[st.top()]){ st.push(i); }else if(heights[i] == heights[st.top()]){ st.push(i); }else{ while(!st.empty() & amp; & amp; heights[i] < heights[st.top()]){ int mid=st.top(); st.pop(); if(!st.empty()){ int left=st.top(); int right=i; int w=right-left-1; int h=heights[mid]; res=max(w*h,res); } } st.push(i); } } return res; } };
