배열 이 지정 한 용기 의 저수량 을 구하 다.

제목 설명
용 기 를 대표 하 는 음수 가 아 닌 배열 을 지정 합 니 다.예 를 들 어 배열 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 은 바로 다음 도형 에서 검은색 부분 이다.이 용기 로 물 을 받 으 면 물 을 얼마나 받 을 수 있 습 니까?이 배열 의 경우 6 칸 의 물 을 받 을 수 있 는데 바로 아래 도형 의 파란색 부분 이다.요구: 시간 복잡 도 O (N), 추가 공간 복잡 도 O (1) 의 해법 을 실현 합 니 다.
일단 간단 한 알고리즘 을 볼 게 요.
해법 1: 보조 배열 사용
원리: 만약 에 제 가 i 번 째 위치 에 있 는 물의 값 을 요구한다 면 i 왼쪽 의 최대 값 과 i 오른쪽 의 최대 값 을 찾 아서 두 개의 배열 L 과 R 로 표시 해 야 합 니 다.그 중에서 L [i] 는 i 앞의 최대 치 를 나타 내 고 R [i] 는 뒤의 최대 치 를 나타 낸다.그 다음 에 두 개의 최대 치 중의 작은 값 을 사용 하여 i 의 값 을 빼 고 i 의 값 이 0 보다 작 으 면 축 적 된 물 은 0 이 고 그렇지 않 으 면 상쇄 후의 값 이다.모든 i 를 왼쪽 에서 오른쪽으로 옮 겨 다 니 기 때문에 매번 i 왼쪽 의 최대 값 은 하나의 값 으로 저장 해 야 합 니 다.시간 복잡 도: O (n), 공간 복잡 도: O (n)publicstaticint maxWater(int[] arr){ if(arr ==null|| arr.length <=2)return0; int maxL = arr[0]; int[] maxR =newint[arr.length]; int max =0; for(int i = arr.length -1; i >=0; i--){ if(arr[i]> max) maxR[i]= max = arr[i]; else maxR[i]= max; }

max =0;//

for(int i =1; i < arr.length -1; i++){

if(arr[i]> maxL) maxL = arr[i];// i max +=Math.max(Math.min(maxL, maxR[i])- arr[i],0); }

return max;

}

：

5 4 … 3 7
| |
， ， ， ， （ ， ， i ， ， i ， ， ）， ， 。
O(N)， O(1)。
：

1. publicstaticint maxWaterWithConstSpace(int[] arr){
if(arr ==null|| arr.length <=2)return0; int maxL = arr[0]; int maxR = arr[arr.length -1]; int max =0;//
2. max =0;
3. int l =1;
int r = arr.length -2;
4. while(l <= r){
if(maxL <= maxR){ max +=Math.max(0, maxL - arr[l]); if(arr[l++]> maxL) maxL = arr[l-1]; }else{ max +=Math.max(0, maxR - arr[r]); if(arr[r--]> maxR) maxR = arr[r +1]; } }
5. return max;
}





(Wiz)





:https://www.cnblogs.com/ggmfengyangdi/p/5706803.html