题目大意:
给你地形的高度,有V单位的水会从K位置落下,问你稳定之后水位的高度。
Problem:
We are given an elevation map, heights[i]
representing the height of the terrain at that index. The width at each index is 1. After V
units of water fall at index K
, how much water is at each index?
Water first drops at index K
and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:
- If the droplet would eventually fall by moving left, then move left.
- Otherwise, if the droplet would eventually fall by moving right, then move right.
- Otherwise, rise at it’s current position.
Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.
We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block – each unit of water has to be in exactly one block.
Idea:
Solution 1: Simulation
Time complexity: O(V*n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 3 ms class Solution { public: vector<int> pourWater(vector<int>& heights, int V, int K) { while (V--) drop(heights, K); return heights; } private: void drop(vector<int>& heights, int K) { int best = K; for (int d = -1; d <= 1; d += 2) { int i = K + d; while (i >= 0 && i < heights.size() && heights[i] <= heights[i - d]) { if (heights[i] < heights[best]) best = i; i += d; } if (best != K) break; } ++heights[best]; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 12 ms class Solution { public int[] pourWater(int[] heights, int V, int K) { while (V-- > 0) { dropWater(heights, K); } return heights; } private void dropWater(int[] heights, int K) { int best = K; for (int d = -1; d <= 1; d += 2) { int i = K + d; while (i >= 0 && i < heights.length && heights[i] <= heights[i - d]) { if (heights[i] < heights[best]) best = i; i += d; } if (best != K) break; } ++heights[best]; } } |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
""" Author: Huahua Running time: 207 ms """ class Solution: def pourWater(self, heights, V, K): def drop(h, K): best = K for d in (-1, 1): i = K + d while i >= 0 and i < len(h) and h[i] <= h[i - d]: if h[i] < h[best]: best = i i += d if best != K: break heights[best] += 1 for _ in range(V): drop(heights, K) return heights |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment