Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Latest commit

 

History

History
History
24 lines (22 loc) · 890 Bytes

File metadata and controls

24 lines (22 loc) · 890 Bytes
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//
// Solution42.cpp
// Algorithm
//
// Created by Pancf on 2020/11/1.
// Copyright © 2020 Pancf. All rights reserved.
//
#include "Solution42.hpp"
int Solution42::trap(std::vector<int> &height)
{
if (height.size() < 3) return 0;
// 从两边向中间遍历,选择从较低一侧倒水,每次倒的水width为1,height为(当前最高水位-当前bar的高度)
// 当前水位和当前bar高度相等时,倒的水为0,所以无需特殊处理
// 因为每次迭代总是固定bar更高的一侧,所以从较低一侧倒水是必然可行的
int waterSum = 0, waterLevel = 0, left = 0, right = (int)height.size() - 1;
while (left < right) {
int lower = height[left] < height[right] ? height[left++] : height[right--];
waterLevel = std::max(waterLevel, lower);
waterSum += waterLevel - lower;
}
return waterSum;
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.