大廠算法面試之leetcode精講13.單調(diào)棧
視頻講解（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)
目錄：
239. 滑動(dòng)窗口最大值 (hard)
方法1.優(yōu)先隊(duì)列
動(dòng)畫(huà)過(guò)大狭莱，點(diǎn)擊查看
- 思路：最大值問(wèn)題我們可以采用大頂堆外盯，具體就是維護(hù)一個(gè)大頂堆，初始的時(shí)候?qū)?code>0～k-1的元素加入堆中扎谎，存入的是值和索引的鍵值隊(duì)路鹰，然后滑動(dòng)窗口從從索引為k的元素開(kāi)始遍歷矾飞，將新進(jìn)入滑動(dòng)窗口的元素加堆中枚冗，當(dāng)堆頂元素不在滑動(dòng)窗口中的時(shí)候姓建，不斷刪除堆頂堆元素诞仓，直到最大值在滑動(dòng)窗口里。
- 復(fù)雜度分析：時(shí)間復(fù)雜度
O(nlogn)速兔，n是nums的長(zhǎng)度墅拭，將一個(gè)元素加入優(yōu)先隊(duì)列的時(shí)間復(fù)雜度是logn，最壞的情況下所有元素都要入隊(duì)涣狗，所以復(fù)雜度是nlogn谍婉。空間復(fù)雜度是O(n)镀钓，最壞的情況下穗熬，所有元素都在隊(duì)列中，所以是O(n)
js:
class Heap {
constructor(comparator = (a, b) => a - b, data = []) {
this.data = data;
this.comparator = comparator;//比較器
this.heapify();//堆化
}
heapify() {
if (this.size() < 2) return;
for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) {
this.bubbleDown(i);//bubbleDown操作
}
}
peek() {
if (this.size() === 0) return null;
return this.data[0];//查看堆頂
}
offer(value) {
this.data.push(value);//加入數(shù)組
this.bubbleUp(this.size() - 1);//調(diào)整加入的元素在小頂堆中的位置
}
poll() {
if (this.size() === 0) {
return null;
}
const result = this.data[0];
const last = this.data.pop();
if (this.size() !== 0) {
this.data[0] = last;//交換第一個(gè)元素和最后一個(gè)元素
this.bubbleDown(0);//bubbleDown操作
}
return result;
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = (index - 1) >> 1;//父節(jié)點(diǎn)的位置
//如果當(dāng)前元素比父節(jié)點(diǎn)的元素小丁溅，就交換當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)的位置
if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
this.swap(index, parentIndex);//交換自己和父節(jié)點(diǎn)的位置
index = parentIndex;//不斷向上取父節(jié)點(diǎn)進(jìn)行比較
} else {
break;//如果當(dāng)前元素比父節(jié)點(diǎn)的元素大唤蔗，不需要處理
}
}
}
bubbleDown(index) {
const lastIndex = this.size() - 1;//最后一個(gè)節(jié)點(diǎn)的位置
while (true) {
const leftIndex = index * 2 + 1;//左節(jié)點(diǎn)的位置
const rightIndex = index * 2 + 2;//右節(jié)點(diǎn)的位置
let findIndex = index;//bubbleDown節(jié)點(diǎn)的位置
//找出左右節(jié)點(diǎn)中value小的節(jié)點(diǎn)
if (
leftIndex <= lastIndex &&
this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
) {
findIndex = leftIndex;
}
if (
rightIndex <= lastIndex &&
this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
) {
findIndex = rightIndex;
}
if (index !== findIndex) {
this.swap(index, findIndex);//交換當(dāng)前元素和左右節(jié)點(diǎn)中value小的
index = findIndex;
} else {
break;
}
}
}
swap(index1, index2) {//交換堆中兩個(gè)元素的位置
[this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
}
size() {
return this.data.length;
}
}
var maxSlidingWindow = function(nums, k) {
let ans = [];
let heap = new Heap((a, b) => b.val - a.val);//大頂堆
for(let i=0;i<k-1;i++) heap.offer({val: nums[i], index: i});//初始的時(shí)候?qū)?～k-1的元素加入堆中
for(let i=k-1; i<nums.length; i++){//滑動(dòng)窗口從從索引為k-1的元素開(kāi)始遍歷
heap.offer({val: nums[i], index: i});//將新進(jìn)入滑動(dòng)窗口的元素加堆中
//當(dāng)堆頂元素不在滑動(dòng)窗口中的時(shí)候，不斷刪除堆頂堆元素，直到最大值在滑動(dòng)窗口里措译。
while(heap.peek().index<=i-k) heap.poll();
ans.push(heap.peek().val);//將在滑動(dòng)窗口里的最大值加入ans
}
return ans;
}
java:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {//大頂堆
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {//初始的時(shí)候?qū)?～k-1的元素加入堆中
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];//滑動(dòng)窗口初始最大值
for (int i = k; i < n; ++i) {//滑動(dòng)窗口從從索引為k的元素開(kāi)始遍歷
pq.offer(new int[]{nums[i], i});//將新進(jìn)入滑動(dòng)窗口的元素加堆中
//當(dāng)堆頂元素不在滑動(dòng)窗口中的時(shí)候别凤，不斷刪除堆頂堆元素，直到最大值在滑動(dòng)窗口里领虹。
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];//將在滑動(dòng)窗口里的最大值加入ans
}
return ans;
}
}
方法2.單調(diào)隊(duì)列
動(dòng)畫(huà)過(guò)大规哪，點(diǎn)擊查看
- 思路：維護(hù)單調(diào)遞減隊(duì)列，當(dāng)進(jìn)入滑動(dòng)窗口的元素大于等于隊(duì)尾的元素時(shí) 不斷從隊(duì)尾出隊(duì)塌衰，直到進(jìn)入滑動(dòng)窗口的元素小于隊(duì)尾的元素诉稍，才可以入隊(duì)，以保證單調(diào)遞減的性質(zhì)最疆，當(dāng)隊(duì)頭元素已經(jīng)在滑動(dòng)窗口外了杯巨，移除對(duì)頭元素，當(dāng)i大于等于k-1的時(shí)候努酸，單調(diào)遞減隊(duì)頭就是滑動(dòng)窗口的最大值
- 復(fù)雜度分析：時(shí)間復(fù)雜度
O(n)服爷，n是nums的長(zhǎng)度，每個(gè)元素入隊(duì)一次获诈∪栽矗空間復(fù)雜度O(k)，隊(duì)列最多存放k大小的元素
js:
var maxSlidingWindow = function (nums, k) {
const q = [];//單遞減的雙端隊(duì)列
const ans = [];//最后的返回結(jié)果
for (let i = 0; i < nums.length; i++) {//循環(huán)nums
//當(dāng)進(jìn)入滑動(dòng)窗口的元素大于等于隊(duì)尾的元素時(shí) 不斷從隊(duì)尾出隊(duì)舔涎，
//直到進(jìn)入滑動(dòng)窗口的元素小于隊(duì)尾的元素笼踩，以保證單調(diào)遞減的性質(zhì)
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop();
}
q.push(i);//元素的索引入隊(duì)
while (q[0] <= i - k) {//隊(duì)頭元素已經(jīng)在滑動(dòng)窗口外了，移除對(duì)頭元素
q.shift();
}
//當(dāng)i大于等于k-1的時(shí)候亡嫌，單調(diào)遞減隊(duì)頭就是滑動(dòng)窗口的最大值
if (i >= k - 1) ans.push(nums[q[0]]);
}
return ans;
};
Java:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
84. 柱狀圖中最大的矩形 (hard)
- 思路：準(zhǔn)備單調(diào)遞增棧存放數(shù)組下標(biāo)嚎于，因?yàn)檫@樣可以從棧頂找到左邊第一個(gè)比自己小的下標(biāo)，這樣從當(dāng)前下標(biāo)出發(fā)到第一個(gè)比自己小的柱子的下標(biāo)就是矩形面積的寬度挟冠，然后在乘當(dāng)前柱子的高度就是面積于购，如果當(dāng)前柱子大于棧頂?shù)南聵?biāo)對(duì)應(yīng)的柱子高度，就入棧圃郊，否則不斷出棧价涝，計(jì)算棧頂?shù)闹铀苄纬傻木匦蚊娣e，然后更新最大矩形面積
- 復(fù)雜度：時(shí)間復(fù)雜度
O(n)持舆，n是heights的長(zhǎng)度色瘩，數(shù)組里每個(gè)元素盡出棧一次∫菰ⅲ空間復(fù)雜度O(n)居兆，棧空間最多為n
動(dòng)畫(huà)過(guò)大竹伸，點(diǎn)擊查看
js：
const largestRectangleArea = (heights) => {
let maxArea = 0
const stack = [] //單調(diào)遞增棧 注意棧存的時(shí)下標(biāo)
heights = [0, ...heights, 0] //在heights數(shù)組前后增加兩個(gè)哨兵 用來(lái)清零單調(diào)遞增棧里的元素
for (let i = 0; i < heights.length; i++) {
//當(dāng)前元素對(duì)應(yīng)的高度小于棧頂元素對(duì)應(yīng)的高度時(shí)
while (heights[i] < heights[stack[stack.length - 1]]) {
const stackTopIndex = stack.pop() //出棧
maxArea = Math.max( //計(jì)算面積 并更新最大面積
maxArea,
heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)//高乘寬
)
}
stack.push(i)//當(dāng)前下標(biāo)加入棧
}
return maxArea
}
java：
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int len = heights.length;
int maxArea = 0;
for(int i = 0; i < len; i++){
if(stack.isEmpty() || heights[stack.peek()] <= heights[i])
stack.push(i);
else{
int top = -1;
while(!stack.isEmpty() && heights[stack.peek()] > heights[i])
{
top = stack.pop();
maxArea = Math.max(maxArea, heights[top] * (i - top));
}
heights[top] = heights[i];
stack.push(top);
}
}
while(!stack.isEmpty())
{
int top = stack.pop();
maxArea = Math.max(maxArea, (len - top) * heights[top]);
}
return maxArea;
}
}
85. 最大矩形 (hard)
方法1.單調(diào)棧
ds_106
- 思路：84題的變種泥栖，從第一行到第n行形成的柱狀圖可以利用84題求解簇宽，然后循環(huán)每一行，計(jì)算以這一行為底的柱狀圖最大面積吧享，然后更新最大矩形面積
- 復(fù)雜度：時(shí)間復(fù)雜度
O(mn)魏割，m、n分別是矩形的高度和寬度钢颂，循環(huán)m次行钞它，每行里循環(huán)每個(gè)柱子的高度∈獗蓿空間復(fù)雜度O(n)遭垛，heights數(shù)組的空間。
js：
var maximalRectangle = function (matrix) {
if (matrix.length == 0) return 0;
let res = 0;
let heights = new Array(matrix[0].length).fill(0);//初始化heights數(shù)組
for (let row = 0; row < matrix.length; row++) {
for (let col = 0; col < matrix[0].length; col++) {
if(matrix[row][col] == '1' ) heights[col] += 1;
else heights[col] = 0;
}//求出每一層的 heights[] 然后傳給84題的函數(shù)
res = Math.max(res, largestRectangleArea(heights));//更新一下最大矩形面積
}
return res;
};
const largestRectangleArea = (heights) => {
let maxArea = 0
const stack = [] //單調(diào)遞增棧 注意棧存的時(shí)下標(biāo)
heights = [0, ...heights, 0] //在heights數(shù)組前后增加兩個(gè)哨兵 用來(lái)清零單調(diào)遞增棧里的元素
for (let i = 0; i < heights.length; i++) {
//當(dāng)前元素對(duì)應(yīng)的高度小于棧頂元素對(duì)應(yīng)的高度時(shí)
while (heights[i] < heights[stack[stack.length - 1]]) {
const stackTopIndex = stack.pop() //出棧
maxArea = Math.max( //計(jì)算面積 并更新最大面積
maxArea,
heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)//高乘寬
)
}
stack.push(i)//當(dāng)前下標(biāo)加入棧
}
return maxArea
}
java：
class Solution {
public int maximalRectangle(char[][] matrix) {
int row = matrix.length;
if (row == 0)
return 0;
int col = matrix[0].length;
int[] heights = new int[col + 1];
heights[col] = -1;
int res = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
heights[j] = matrix[i][j] == '1' ? heights[j] + matrix[i][j] - '0' : 0;
}
res = Math.max(res, largestRectangleArea(Arrays.copyOf(heights, col + 1)));
}
return res;
}
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int len = heights.length;
int maxArea = 0;
for (int i = 0; i < len; i++) {
if (stack.isEmpty() || heights[stack.peek()] <= heights[i])
stack.push(i);
else {
int top = -1;
while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
top = stack.pop();
maxArea = Math.max(maxArea, heights[top] * (i - top));
}
heights[top] = heights[i];
stack.push(top);
}
}
return maxArea;
}
}
496. 下一個(gè)更大元素 I (easy）
動(dòng)畫(huà)過(guò)大操灿，點(diǎn)擊查看
- 思路：
- 循環(huán)nums2锯仪，如果循環(huán)的元素大于棧頂元素，并且棧不為空趾盐，則不斷將棧頂元素作為key庶喜，當(dāng)前元素作為value加入map中
- 本質(zhì)是第一個(gè)比棧頂元素大的值會(huì)讓棧中的元素不斷出隊(duì) 所以這個(gè)數(shù)就是這些出棧元素的下一個(gè)更大的數(shù)
- 剩下來(lái)的元素就是沒(méi)有找到最大值的
- 遍歷nums1將結(jié)果推入ans中
- 復(fù)雜度：時(shí)間復(fù)雜度
O(m+n)，nums1谤碳、nums2遍歷一遍溃卡，nums2中的元素入隊(duì)出隊(duì)一次溢豆⊙鸭颍空間復(fù)雜度O(n)，椾鱿桑空間和map的空間的復(fù)雜度
js：
let nextGreaterElement = function(nums1, nums2) {
let map = new Map(), stack = [], ans = [];
//循環(huán)nums2搓茬，如果循環(huán)的元素大于棧頂元素，并且棧不為空队他，則不斷將棧頂元素作為key卷仑，當(dāng)前元素作為value加入map中
//本質(zhì)是第一個(gè)比棧頂元素大的值會(huì)讓棧中的元素不斷出隊(duì) 所以這個(gè)數(shù)就是這些出棧元素的下一個(gè)更大的數(shù)
nums2.forEach(item => {
while(stack.length && item > stack[stack.length-1]){
map.set(stack.pop(), item)
};
stack.push(item);
});
stack.forEach(item => map.set(item, -1));//剩下來(lái)的元素就是沒(méi)有找到最大值的
nums1.forEach(item => ans.push(map.get(item)));//遍歷nums1將結(jié)果推入ans中
return ans;
};
java：
public class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
Deque<Integer> stack = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len2; i++) {
while (!stack.isEmpty() && stack.peekLast() < nums2[i]) {
map.put(stack.removeLast(), nums2[i]);
}
stack.addLast(nums2[i]);
}
int[] ans = new int[len1];
for (int i = 0; i < len1; i++) {
ans[i] = map.getOrDefault(nums1[i], -1);
}
return ans;
}
}
42. 接雨水 （hard）
-
思路：首先考慮暴力做法，找找思路麸折，暴力做法可以遍歷數(shù)組锡凝，在每個(gè)位置分別往兩邊尋找左柱子中的最大高度和右柱子中的最大高度，找到之后垢啼，用左右最大高度的較小者減去當(dāng)前柱子的高度窜锯，就是當(dāng)前位置能接的水量。該方法要循環(huán)整個(gè)數(shù)組芭析，并且每個(gè)位置要遍歷數(shù)組尋找左右柱子高度的最大值锚扎，嵌套了一層循環(huán)，所以復(fù)雜度是
O(n^2)馁启。我們?cè)鯓蛹铀偾短椎倪@層循環(huán)呢驾孔，其實(shí)可以預(yù)先計(jì)算從左往右和從右往左的最大高度數(shù)組，在循環(huán)數(shù)組的時(shí)候，可以直接拿到該位置左右兩邊的最大高度翠勉，當(dāng)前位置的接水量就是左右兩邊高度的較小者減去當(dāng)前位置柱子的高度
復(fù)雜度：時(shí)間復(fù)雜度
O(n)妖啥，尋找左右的最大高度，循環(huán)計(jì)算每個(gè)位置的接水量对碌，總共3個(gè)循環(huán)迹栓，但他們不是嵌套關(guān)系〖蠡海空間復(fù)雜度是O(n)克伊，n是heights數(shù)組，用到了leftMax和rightMax數(shù)組华坦，即存放左右兩邊最大高度的數(shù)組愿吹。
方法1.動(dòng)態(tài)規(guī)劃
動(dòng)畫(huà)過(guò)大，點(diǎn)擊查看
js：
var trap = function(height) {
const n = height.length;
if (n == 0) {//極端情況
return 0;
}
const leftMax = new Array(n).fill(0);//初始化從左往右看的最大值數(shù)組
leftMax[0] = height[0];
for (let i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
const rightMax = new Array(n).fill(0);//初始化從右往左看的最大值數(shù)組
rightMax[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
let ans = 0;
//循環(huán)數(shù)組惜姐，每個(gè)位置能接的雨水量就是這個(gè)位置左右最大值的較小者減去當(dāng)前的高度
for (let i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
};
java：
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
方法2:單調(diào)棧
動(dòng)畫(huà)過(guò)大犁跪，點(diǎn)擊查看
- 思路：遍歷
heights數(shù)組，將其中的元素加入單調(diào)遞減棧歹袁，如果當(dāng)前柱子的高度大于棧頂柱子的高度坷衍， 不斷出棧，相當(dāng)于找到左邊比當(dāng)前柱子矮的位置条舔，然后每次出棧之后都要累加一下面積枫耳。 - 復(fù)雜度：時(shí)間復(fù)雜度
O(n)，n是heights的長(zhǎng)度孟抗，數(shù)組中的每個(gè)元素最多入棧出棧一次迁杨。空間復(fù)雜度O(n)凄硼，棧的空間铅协，最多不會(huì)超過(guò)heights的長(zhǎng)度
js：
var trap = function(height) {
let ans = 0;
const stack = [];//單調(diào)遞減棧。存放的是下標(biāo)哦
const n = height.length;
for (let i = 0; i < n; ++i) {//循環(huán)heights
//當(dāng)前柱子的高度大于棧頂柱子的 不斷出棧
while (stack.length && height[i] > height[stack[stack.length - 1]]) {
const top = stack.pop();
if (!stack.length) {//棧為空時(shí) 跳出循環(huán)
break;
}
const left = stack[stack.length - 1];//拿到當(dāng)前位置左邊比當(dāng)前柱子矮的位置
const currWidth = i - left - 1;//計(jì)算寬度
const currHeight = Math.min(height[left], height[i]) - height[top];//計(jì)算高度
ans += currWidth * currHeight;//計(jì)算當(dāng)面積
}
stack.push(i);//加入棧
}
return ans;
};
java：
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
}
}
方法3.雙指針
動(dòng)畫(huà)過(guò)大摊沉，點(diǎn)擊查看
- 思路：如果右邊存在一個(gè)比當(dāng)前高的柱子狐史，就會(huì)形成一個(gè)洼地，同理说墨，左邊存在一個(gè)比當(dāng)前高柱子骏全，也會(huì)形成一個(gè)坑，用雙指針循環(huán)
heights數(shù)組婉刀，判斷是否形成洼地吟温，如果能形成洼地，則計(jì)算積水量突颊，累加進(jìn)ans鲁豪。 - 復(fù)雜度：時(shí)間復(fù)雜度
O(n)潘悼，n為heights的長(zhǎng)度， 總共遍歷heights一次爬橡≈位剑空間復(fù)雜度O(1)，只用到了兩個(gè)指針
js：
var trap = function(height) {
let ans = 0;
let left = 0, right = height.length - 1;//初始化雙指針
let leftMax = 0, rightMax = 0;//左右兩邊最大高度
while (left < right) {//循環(huán)雙指針
leftMax = Math.max(leftMax, height[left]);//左邊最大值
rightMax = Math.max(rightMax, height[right]);//右邊最大值
if (height[left] < height[right]) {//右邊的柱子高于左邊的柱子 計(jì)算這個(gè)位置的接水量 累加進(jìn)結(jié)果
ans += leftMax - height[left];
++left;
} else { //左邊的柱子高于或等于右邊的柱子 計(jì)算這個(gè)位置的接水量 累加進(jìn)結(jié)果
ans += rightMax - height[right];
--right;
}
}
return ans;
};
java：
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
}
