計(jì)算數(shù)組中每個(gè)數(shù)左邊第一個(gè)比其大的值
如果用最簡(jiǎn)單的暴力法似芝，時(shí)間復(fù)雜度最壞情況下 O(n^2)
用棧解決悠反，遍歷到a[i]
- 當(dāng)棧中為空铺然，直接壓入
- 棧不為空疙渣，比較棧頂元素 top 和 a[i]撇吞。 若 top < a[i] 俗冻，彈出棧頂元素。循環(huán)執(zhí)行牍颈，直到遇到第一個(gè) top>a[i] （top即為第一個(gè)比其大的元素）或者 棧為空（左邊沒(méi)有比 a[i] 大的元素）
因此棧中元素從底到上按照從大到小的順序
for (int index = 0; index < length; index++) {
while (!stack.isEmpty() && arr[index] >= stack.peek()) {
stack.pop();
}
if (!stack.isEmpty()) {
leftFirstMax[index] = stack.peek();
}
stack.push(arr[index]);
}
計(jì)算數(shù)組中每個(gè)數(shù)右邊第一個(gè)比其大的值
思路完全一樣迄薄，只不過(guò)遍歷的順序從右到左
// 棧中從棧底到棧頂 順序,從右往左遍歷，計(jì)算每個(gè)數(shù)右邊第一個(gè)比其大的值
for (int index = length - 1; index >= 0; index--) {
while (!stack.isEmpty() && arr[index] >= stack.peek()) {
stack.pop();
}
if(!stack.isEmpty()){
rightFirstMax[index]= stack.peek();
}
}
計(jì)算數(shù)組中每個(gè)數(shù)左邊第一個(gè)比其小的值
思路與 1 相同煮岁，只不過(guò)棧中元素從底到上按照從小到大的順序
