接雨水

Jan 2, 2023

今天重新开始写动态规划，又看到这道经典的题目，之所以称之为经典，是因为题目确实比较巧妙地适用于多种算法，而不是某些题那样硬套。既然是动态规划，就先用动态规划的思路来分析一下这道题。每个点的可接雨水量取决于点左边的最高点以及右边最高点的较小值，所以关键在于，我们要求得每个点左边的最大值，以及右边的最大值，那么只需要正逆向遍历两次，得到这两个数组以后将每个点的较小值减去这个点的高度，就是这个点可以积蓄雨水的量了。

public int trap(int[] height) {
    int len = height.length;
    int [] lefthighest = new int[len+1];
    int [] righthighest = new int[len+1];
    righthighest[len-1] = height[len-1];
    lefthighest[0] = height[0];
    for(int i = 1 ; i < len ; i  ++){
        lefthighest[i] = Math.max(lefthighest[i-1],height[i]);
        righthighest[len-i-1] = Math.max(righthighest[len-i],height[len-i-1]);
    }
    int ans = 0;
    for(int i = 1 ; i < len-1 ; i ++){
        ans += Math.max(0,Math.min(lefthighest[i-1],righthighest[i+1])-height[i]);
    }
    return ans;
}

接雨水这题应该也不用多说了，经典中的经典题，在我上大学那会就已经是google经典面试题，那时候我对DP还是一头雾水，更别说这题还有三种解法，DP、单调栈、双指针。

这里先只说单调栈这种数据结构，因为这种解法算是最直观的解法了，另外两种相对更巧妙也不能说一道题能总结下来的。

所谓单调栈其实就是一个只保存单调序列的栈，通过不断地维护栈的过程，我们可以解决一些特定的问题，例如找到数组中每一个数的下一个更大的数，其原理很简单，比栈顶的数小就进栈，比栈顶大就将栈里所有小于当前数的值全部出栈并且进行一些操作，通常我们对这些数进行进栈出栈时一般用下标保存，这样更方便操作。

vector<int> nextGreaterElement(vector<int>&nums1,vector<int>& nums2){
	int len1 = nums1.size();
	int len2 = nums2.size();
	unordered_map<int,int> map;
	stack<int> stk;
	for(int i = 0 ; i < len2 ; i ++){
		while(!stk.empty()&&nums2[stk.top()]<nums2[i]){
			int j = stk.top();stk.pop();
			map.emplace(nums2[j],nums2[i]);
		}
		stk.push(i);
	}
	vector<int>ans;
	for(int i = 0 ; i < len1 ; i ++){
		if(map.count(nums1[i])){
			ans.emplace_back(map[nums1[i]]);
		}else{
			ans.emplace_back(-1);
		}
	}
	return ans;
}