題意：給定兩個數(shù)組词疼，boxes記錄box的高和warehouse記錄warehouse的高甥绿，問warehouse中最多放幾個box
思路：
- 把box排序
- 創(chuàng)建一個stack勇蝙，從頭到尾遍歷warehouse
- 如果stack空嚎研，把warehouse[i]的index放進去
- 如果stack不空且stack頂?shù)母叨?gt;warehouse[i]许饿，把warehouse[i]的index放進去
- 從頭到尾遍歷box噩凹，具體見代碼注釋
思想：棧
復(fù)雜度：時間O（nlgn）巴元，空間O（n）
int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
// 輸入?yún)?shù)的null和empty檢查，此處忽略了
Arrays.sort(boxes);
Stack<Integer> stack = new Stack();
// 初始化stack
for(int i=0;i<warehouse.length;i++) {
if(stack.isEmpty() || warehouse[stack.peek()] > warehouse[i]) {
stack.add(i);
}
}
int result = 0;
int pre = warehouse.length;
for(int i=0;i<boxes.length;i++) {
// 獲取當(dāng)前stack的頂部值
int temp = warehouse[stack.peek()];
// 當(dāng)前的box的最小高度小于stack的頂部值
if(boxes[i] <= temp) {
// 獲取可用的warehouse數(shù)目
int cnt = pre - stack.peek();
// 把符合條件的box放入warehouse
while(i<boxes.length && boxes[i] <= temp && cnt > 0) {
result++;
i++;
cnt--;
}
i--;
}
// 更新pre
pre = stack.pop();
}
return result;
}
