leetcode-单调栈26

关于单调栈的顺序总结： 

寻找右边第一个比我大的：从左到右遍历，栈单调递减
寻找左边第一个比我小的：从左到右遍历，栈单调递增
寻找右边第一个比我小的：从右到左遍历，栈单调递增
寻找左边第一个比我大的：从右到左遍历，栈单调递减

找哪边的就从哪边遍历（需要优先处理边界），找小的就单调递增（栈底小栈顶大）；找大的就单调递减（栈底大栈顶小）。汉诺塔

遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。

例如 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;
}