控制器的功能是解释指令(完成指令)、保证指令的按序执行。
次元门(\\v\\):
接雨水问题 , 三种解法.
NO 1: 单调栈.
对单调栈的回退(出栈)过程进行模拟 , 就可很明确的得到计算过程.
class Solution { public: int trap(vector<int>& height) { int n = height.size() , re = 0 , left = 0; stack<int>sta; for(int i = 0;i < n;i ++){ while(!sta.empty() && height[i] > height[sta.top()]){ int cnt = sta.top(); sta.pop(); if(sta.empty()) break; int left = sta.top(); int col = i - left - 1; int row = min(height[left] , height[i]) - height[cnt]; re += col * row; } sta.push(i); } return re; } };
NO 2: dp 动态规划
从左往右遍历: 假设最右端存在一个 无限高 的柱子 , 计算每个柱子最多可以积累的水;
从右往左遍历: 假设最左端存在一个 无限高 的柱子 , 计算每个柱子最多可以积累的水;
取 min - height 就是该单元格能接的水.
class Solution { public: int trap(vector<int>& height) { int n = height.size() , re = 0; vector<int>dp_left(n , 0); int left = height[0]; vector<int>dp_right(n , 0); int right = height[n - 1]; for(int i = 0;i < n;i ++){ left = max(left , height[i]); dp_left[i] = left; } for(int i = n - 1;i >= 0;i --){ right = max(right , height[i]); dp_right[i] = right; } for(int i = 0;i < n;i ++){ re += min(dp_right[i] , dp_left[i]) - height[i]; } return re; } };
NO 3: 双指针