Fish:
N voracious fish are moving along a river. Calculate how many fish are alive.
You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.
The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.
Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:
- 0 represents a fish flowing upstream,
- 1 represents a fish flowing downstream.
If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:
- If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
- If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.
We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.
For example, consider arrays A and B such that: A[0] = 4 B[0] = 0 A[1] = 3 B[1] = 1 A[2] = 2 B[2] = 0 A[3] = 1 B[3] = 0 A[4] = 5 B[4] = 0
Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.
Write a function:
class Solution { public int solution(int[] A, int[] B); }
that, given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.
For example, given the arrays shown above, the function should return 2, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [0..1,000,000,000];
- each element of array B is an integer that can have one of the following values: 0, 1;
- the elements of A are all distinct.
這題一開始想單純用陣列移位去解，但後來發現如果連續的多個0或1的方向會有問題，所以放棄這個方式。
後來又用一個Stack存編號，一個Stack存方向，然後迴圈取下一個值判斷，並且將有可能的方向性都寫出來，但還是會漏掉了吃掉下游魚的魚。
一直到參考到別人的寫法，才發現自己的判斷改一下就可以了，先判斷是否為上游魚，是的話則判斷有沒有阻礙牠的下游魚，如果有就判斷誰吃誰，沒有就保存在Stack，若下游魚的Stack不為空則迴圈判斷，若下游魚比上游魚小則將Stack做pop，反之則break，然後繼續比對下一個陣列中的魚，最後再將兩個Stack的數量加起來就是存活的魚。
public static int fish(int[] a, int[] b) {
Stack<Integer> down = new Stack<>();
Stack<Integer> up = new Stack<>();
for (int i = 0; i < b.length; i++) {
if (b[i] == 0) {
while (!down.isEmpty()) {
if (down.peek() < a[i]) {
down.pop();
} else {
break;
}
}
if (down.isEmpty()) {
up.push(a[i]);
}
} else {
down.push(a[i]);
}
}
return up.size() + down.size();
}
Cheng® 