算法训练Day58-创新互联

LeetCode 739. 每日温度

题目链接:739. 每日温度

在山亭等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供网站建设、成都网站建设 网站设计制作按需设计网站,公司网站建设,企业网站建设,成都品牌网站建设,营销型网站,成都外贸网站制作,山亭网站建设费用合理。

思路:本题可以使用暴力解法,两层for循环,但终归是不美,这种可以使用暴力解法搜索数组元素之间关系的情况,可以使用单调栈的思想。单调栈的本质是空间换时间,因为在遍历的过程中需要用一个栈来记录右边(或左边)第一个比当前元素高的元素,因为存储了之前遍历的信息,所以单调栈只需要遍历一次。
本题是要找到一个元素的右边第一个比自身大的元素,所以我们应该使用递增栈。接下来有三种情况:

  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
    直接将当前遍历元素入栈。
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
    因为本题要求的是大于自身的元素,所以等于的时候同第一种情况相同,入栈。
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
    将栈顶元素弹出,并将当前遍历元素持续与新的栈顶元素比较,直到遇到上述两种情况或者该元素成为栈顶元素为止。

go版本:

func dailyTemperatures(temperatures []int) []int {n := len(temperatures)
    res := make([]int, n)
    stack := make([]int, 0)
    for i := 0; i< n; i++ {temp := temperatures[i]
        // 当前遍历的元素T[i]大于栈顶元素T[st.top()]
        for len(stack) >0 && temp >temperatures[stack[len(stack)-1]] {prev := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[prev] = i - prev
        }
        stack = append(stack, i)
    }
    return res
}

LeetCode 496. 下一个更大元素 I

题目链接:496. 下一个更大元素 I

思路:本题与上一题思路一致,仍然使用递增的单调栈来做,但此题多了一些细节上的处理。
首先,我们需要根据题目要求初始化一个数组res用来存放结果,数组长度与nums1一样大小,并且全部初始化为-1。第二个关键就是,题目中说是两个没有重复元素的数组 nums1 和 nums2,那我们可以构建一个哈希表来存放nums1的值,这样之后循环判断的时候就可以根据数值快速找到其对应的下标,还可以判断nums2中的元素是否在nums1中出现过。
接下来同上一题一样,会遇到三种情况:

  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
    直接将当前遍历元素入栈。
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
    因为本题要求的是大于自身的元素,所以等于的时候同第一种情况相同,入栈。
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
    将栈顶元素弹出,并将当前遍历元素持续与新的栈顶元素比较,直到遇到上述两种情况或者该元素成为栈顶元素为止。这个地方还要明确一点,此时遍历的栈顶元素在nums2中右面第一个大的元素即是nums2[i],也就是当前的遍历元素。

go版本:

func nextGreaterElement(nums1 []int, nums2 []int) []int {res := make([]int, len(nums1))
    for i := range res {res[i] = -1
    }
    mp := map[int]int{}
    for i,v := range nums1 {mp[v] = i
    }

    stack := []int{}
    stack = append(stack, 0)

    for i:=1; ifor len(stack)>0 && nums2[i] >nums2[stack[len(stack)-1]] {top := stack[len(stack)-1]
            if _, ok := mp[nums2[top]]; ok {index := mp[nums2[top]];
                res[index] = nums2[i]
            }
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    } 
    return res
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享名称:算法训练Day58-创新互联
网页链接:http://pwwzsj.com/article/jdjci.html