每⽇温度(LeetCode 739)
题目解析:此题的题目出的字面意思是数组中的各个元素下标代表各个天数,元素值代表当前天数的温度,问数组中当前天的温度几天后,温度可以超过当前天的温度,比如:温度23的下标为0,则表示第0天温度为23度,温度24的下标为1,24大于23度,所以,一天后温度就超过了,所以23的对应值为1。
解题思路(注意都是与栈顶元素进行比较)
此题的思路总结就是遍历数组将数组的下标入栈,遍历时取栈顶与当前数组遍历值比较,若当前数组遍历值大于栈顶对应数组值,则将栈顶出栈,循环栈取新的栈顶与当前数组值比较,直到栈顶大于当前数组值跳出循环,将当前数组值下标入栈
1).新建一个栈,遍历数组,从23开始,压入其下标
2).24比23大,很容易得出23对应的结果是1,将23的下标出栈,将24的下标入栈,24比较25同理得出24对应结果为1,25下标压入栈
3).21比25小,继续压入栈,19比21小,22比19大,因此19对应的结果为1,19下标出栈,继续比较
4).22比21大,可得21对应的结果为2,22比25小,其22下标入栈,26比22大,因此22的结果为1,22下标出栈,继续比较,25比26小,得25对应结果为4,25下标出栈,栈内为空,将26下标入栈
5)...按照上面逻辑依次比较,遍历完后查看栈内是否还有元素,依次出栈,其对应结果均为0
算法复杂度是O(n)
具体代码实现:
class Code{
public function temperUpDay($arr){
//定义栈数组
$stack = array();
//定义天数结果数组
$arrDay = array();
foreach ($arr as $key => $value) {
if(empty($stack)){
//将目标数组的第一个元素下标入栈
$stack[] = $key;
}else{
//当栈内不为空时循环出栈
while (!empty($stack)) {
$intEnd = end($stack);
$intEndValue = $arr[$intEnd];
//当栈中元素下标对应值小于当前数组值时,出栈
if($intEndValue < $value){
$arrDay[$intEnd] = $key-$intEnd;
array_pop($stack);
}else{
//栈顶元素对应数组值大于当前数组值时,跳出栈循环,将当前元素下标入栈
break;
}
}
//跳出栈循环后将当前元素下标入栈
$stack[] = $key;
}
}
//当栈不为空,则将剩余栈的数组对应值的天数设为0
while (!empty($stack)) {
$intEnd = end($stack);
$intEndValue = $arr[$intEnd];
$arrDay[$intEnd] = 0;
array_pop($stack);
}
ksort($arrDay);
return $arrDay;
}
}
$obj = new Code();
$arrRet = $obj->temperUpDay(array(23,24,25,21,19,22,26,23));
print_r($arrRet);
输出温度对应结果:
结果
网友评论