關于單調棧的順序總結：?
尋找右邊第一個比我大的：從左到右遍歷，棧單調遞減
尋找左邊第一個比我小的：從左到右遍歷，棧單調遞增
尋找右邊第一個比我小的：從右到左遍歷，棧單調遞增
尋找左邊第一個比我大的：從右到左遍歷，棧單調遞減找哪邊的就從哪邊遍歷（需要優先處理邊界），找小的就單調遞增（棧底小棧頂大）；找大的就單調遞減（棧底大棧頂小）。漢諾塔
遇到相同的元素，更新棧內下標，就是將棧里元素（舊下標）彈出，將新元素（新下標）加入棧中。
例如 5 5 1 3 這種情況。如果添加第二個5的時候就應該將第一個5的下標彈出，把第二個5添加到棧中。
leetcode-739-每日溫度
單調棧：當要入棧元素大于棧頂元素時，更新棧頂元素中res的值，并將棧頂元素移除
? ? ? ? ? ? ? ?當要入棧元素小于棧頂元素時，直接入棧
判別是否需要使用單調棧，如果需要找到左邊或者右邊第一個比當前位置的數大或者小，則可以考慮使用單調棧
模擬過程：
當i = 0時，單調棧為空，將0進棧
? ? ? ? stack = { 0(73) }
? ? ? ? ans = {0,0,0,0,0,0,0,0}
當i = 1時，由于74大于73，因此移除棧頂元素0，賦值ans[0] = 1-0，將1入棧
? ? ? ? stack = { 1(74) }
? ? ? ? ans = {1,0,0,0,0,0,0,0}
當i = 2時，由于75大于74，因此移除棧頂元素1，賦值ans[1] = 2-1，將2入棧
? ? ? ? stack = { 2(75) }
? ? ? ? ans = {1,1,0,0,0,0,0,0}
當i = 3時，由于71小于75，將3入棧
? ? ? ? stack = { 2(75)，3(71) }
? ? ? ? ans = {1,1,0,0,0,0,0,0}
當i = 4時，由于69小于71，將4入棧
? ? ? ? stack = { 2(75)，3(71) ，4(69)}
? ? ? ? ans = {1,1,0,0,0,0,0,0}
當i = 5時，由于72大于69和71，因此依次移除棧頂元素4和3，賦值ans[4] = 5-4 和 ans[3] = 5-3，將5入棧
? ? ? ? stack = { 2(75) ，5(72)}
? ? ? ? ans = {1,1,0,2,1,0,0,0}
當i = 6時，由于76大于72和75，因此依次移除棧頂元素5和2，賦值ans[5] = 6-5 和 ans[2] = 6-2，將6入棧
? ? ? ? stack = { 6(76) }
? ? ? ? ans = {1,1,0,2,1,1,0,0}
當i = 7時，由于73小于76，將7入棧
? ? ? ? stack = {6(76)，7(73)}
? ? ? ? ans = {1,1,4,2,1,1,0,0}
typedef struct stkNode{int val;int index;
}stkNode;stkNode* getNode(int val, int i){stkNode* node = (stkNode*)malloc(sizeof(stkNode));node->val = val;node->index = i;return node;
}int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {stkNode** stk = (stkNode**)malloc(sizeof(stkNode*)*temperaturesSize);int stk_top = 0;int* res = (int*)malloc(sizeof(int)*temperaturesSize);memset(res,0,sizeof(int)*temperaturesSize);for(int i = 0 ; i < temperaturesSize ; i++){stkNode* node = getNode(temperatures[i],i);while(stk_top > 0 && temperatures[i] > stk[stk_top-1]->val){stk_top--;int k = stk[stk_top]->index;res[k] = i-k;}stk[stk_top++] = node;}*returnSize = temperaturesSize;return res;
}
leetcode-496-下一個更大元素I
typedef struct stkNode {int val;int index;
}stkNode;stkNode* getNode(int val, int index) {stkNode* node = (stkNode*)malloc(sizeof(stkNode));node->val = val;node->index = index;return node;
}int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {stkNode* stk[1000];int stk_top = 0;int next[nums2Size];for(int i = 0 ; i < nums2Size ; i++){next[i] = 0;}for (int i = 0; i < nums2Size; i++) {stkNode* node = getNode(nums2[i], i);while (stk_top > 0 && nums2[i] > stk[stk_top - 1]->val) {stk_top--;int k = stk[stk_top]->index;next[k] = nums2[i];}stk[stk_top++] = node;}int* res = (int*)malloc(sizeof(int)*nums1Size);*returnSize = nums1Size;for(int i = 0 ; i < nums1Size ; i++){res[i] = 0;}for (int i = 0; i < nums1Size; i++) {for (int j = 0; j < nums2Size; j++) {if (nums1[i] == nums2[j]) {res[i] = next[j];}}if (res[i] == 0) {res[i] = -1;}}return res;
}leetcode-503-下一個更大元素II
將循環數組拉直，前n-1個元素復制到數組末尾
int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {*returnSize = numsSize;if(numsSize == 0)return NULL;int* res = (int*)malloc(sizeof(int)*numsSize);memset(res,-1,sizeof(int)*numsSize);int stk[2*numsSize-1];int stk_top = 0;for(int i = 0 ; i < 2*numsSize-1 ; i++){while(stk_top > 0 && nums[i%numsSize] > nums[stk[stk_top-1]]){stk_top--;res[stk[stk_top]] = nums[i%numsSize];}stk[stk_top++] = i%numsSize;}return res;
}leetcode-42-接雨水
1.雙指針
列4 左側最高的柱子是列3，高度為2。
列4 右側最高的柱子是列7，高度為3。
列4 柱子的高度為1（以下用height表示）
那么列4的雨水高度為 列3和列7的高度最小值減列4高度，即： min(lHeight, rHeight) - height。列4的雨水高度求出來了，寬度為1，相乘就是列4的雨水體積了。
一樣的方法，只要從頭遍歷一遍所有的列，然后求出每一列雨水的體積，相加之后就是總雨水的體積了。
首先從頭遍歷所有的列，并且要注意第一個柱子和最后一個柱子不接雨水，
當前列雨水面積：min(左邊柱子的最高高度，記錄右邊柱子的最高高度) - 當前柱子高度。
為了得到兩邊的最高高度，使用了雙指針來遍歷
當前位置，左邊的最高高度是前一個位置的左邊最高高度和本高度的最大值。
即從左向右遍歷：maxLeft[i] = max(height[i], maxLeft[i - 1]);
從右向左遍歷：maxRight[i] = max(height[i], maxRight[i + 1]);
int trap(int* height, int heightSize) {int maxLeft[heightSize];int maxRight[heightSize];maxLeft[0] = height[0];maxRight[heightSize-1] = height[heightSize-1];for(int i = 1 ; i < heightSize ; i++){maxLeft[i] = fmax(height[i],maxLeft[i-1]);}for(int i = heightSize-2 ; i >= 0 ; i--){maxRight[i] = fmax(height[i],maxRight[i+1]);}int area = 0;for(int i = 1 ; i < heightSize-1 ; i++){int high = fmin(maxLeft[i],maxRight[i])-height[i];area += high;}return area;
}單調棧
int trap(int* height, int heightSize) {if(heightSize == 0)return 0;int ans = 0;int stk[heightSize];int top = 0;for(int i = 0 ; i < heightSize ; i++){while(top && height[i] > height[stk[top-1]]){int stk_top = stk[--top];if(!top){break;}int left = stk[top-1];int curWidth = i-left-1;int curHeight = fmin(height[left],height[i]) - height[stk_top];ans += curWidth*curHeight;}stk[top++] = i;}return ans;
}leetcode-84-柱狀圖中最大的矩形
首先我們枚舉某一根柱子 i 作為高 h=heights[i]；
隨后我們需要進行向左右兩邊擴展，使得擴展到的柱子的高度均不小于 h。換句話說，我們需要找到左右兩側最近的高度小于 h 的柱子，這樣這兩根柱子之間（不包括其本身）的所有柱子高度均不小于 h，并且就是 i 能夠擴展到的最遠范圍。?
利用哨兵下標
int largestRectangleArea(int* heights, int heightsSize) {int* leftMin = (int*)malloc(sizeof(int)*(heightsSize+1));int* rightMin = (int*)malloc(sizeof(int)*(heightsSize+1));for(int i = 0 ; i <= heightsSize ; i++){leftMin[i] = -1;rightMin[i] = heightsSize;}int stk[heightsSize];int stk_top = 0;for(int i = 0 ; i < heightsSize ; i++){while(stk_top > 0 && heights[i] < heights[stk[stk_top-1]]){stk_top--;rightMin[stk[stk_top]] = i;}stk[stk_top++] = i;}memset(stk,0,sizeof(int)*heightsSize);stk_top = 0;for(int i = heightsSize-1 ; i >= 0 ; i--){while(stk_top > 0 && heights[i] < heights[stk[stk_top-1]]){stk_top--;leftMin[stk[stk_top]] = i;}stk[stk_top++] = i;}int ans = 0;for(int i = 0 ; i < heightsSize ; i++){ans = fmax(ans,(rightMin[i]-leftMin[i]-1)*heights[i]);}return ans;
}?
