php刷每⽇温度(LeetCode 739)

每⽇温度(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);

输出温度对应结果：

结果